Minimal addition to strongly connected graph

Question

I have a set of nodes and set of directed edges between them. The edges have no weight.

How can I found minimal number of edges which has to be added to make the graph strongly connected (ie. there should be a path from every node to all others)? Does this problem have a name?

Answer 1

It's a really classical graph problem.

1. Run algorithm like Tarjan-SCC algorithm to find all SCCs. Consider each SCC as a new vertice, link a edge between these new vertices according to the origin graph, we can get a new graph. Obviously, the new graph is a Directed Acyclic Graph(DAG).
2. In the DAG, find all vertices whose in-degree is 0, we define them {X}; find all vertices whose out-degree is 0, we define them {Y}.
3. If DAG has only one vertice, the answer is 0; otherwise, the answer is max(|X|, |Y|).