Strongly connected component

Question

Given total number of V vertices and total number of E edges of a graph G, how can I compute largest strongly connected component with minimum number of vertices & edges in strongly connected component of graph.

Eg. for graph with 5 vertices and 7 edges, the minimum size of connected component is 3.
This graph can be modeled so that there are more connected components but minimum is 3.

The problem I am facing is that edge information is not given to me. Only the total number of edges are given. I wanted to use Tarjan's algorithm using depth first search but I need edge information.

Is it possible to find the size of strongly connected component with minimum vertices and edges just total number of vertices and total number of edges.

Answer 1

Simplest way I can think of is to consider trying to utilise the edges to form components that are Complete Graphs of size 1, then 2, etc until you find one that works.

A complete graph of size n has (n² - n) / 2 edges. So to split into components of size n will look something like

numFullComponents := V/n //integer division
numEdgesUsed := numFullComponents * n * (n-1) / 2 //This is edges from full components
    + (V%n) * (V%n - 1)/2 //a complete graph on the remainder nodes

You can then compare that number of edges used with the number of edges in the graph. The smallest n that uses at least E edges is the solution.