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!

Are the edges bi-directional? – Said A. Sryheni Dec 17 '17 at 07:49 — Said A. Sryheni, Dec 17 '17 at 07:49
As a hint, arrange the edges in a directed cycle. – templatetypedef Dec 17 '17 at 07:52 — templatetypedef, Dec 17 '17 at 07:52

Said A. Sryheni · Answer 1 · 2018-01-04T08:26:35.893

2

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.

edited Jan 04 '18 at 08:26

answered Dec 17 '17 at 07:57

Said A. Sryheni

697
1
9
29

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

1 Answers1