Finding the maximum number of nodes are strongly connected, given number of nodes and edges

Question

"Given the number of nodes and the number of edges connecting these nodes, arrange these edges such that maximum number of nodes are strongly connected. Return the number of nodes that could be strongly connected."

I am wondering if is there a formula for this? if not, how could I solve this problem? any help would be appreciated!

Answer 1

• If the edges are undirected, then the answer is simply:

  min(number of nodes, number of edges + 1)

  This is because you should arrange the nodes and edges to form a tree graph.

• If the edges are directed, then the answer is simply:

  min(number of nodes, number of edges)

  This is because you should arrange the graph in a straight line and connect the last node with the first one forming a circle-like shape.