Make graph rooted

Question

definition for the question: a node v will be called "root" iff for each node u in the graph there is a directed path from v to u.

given a directed graph G= without any "root" in it.

i need to find an algorithm that decides if we can add one edge so that there will be a "root" in the resulting graph.

any thoughts?

Answer 1

Compute the strongly connected component (SCC) graph for your graph. If that SCC graph has exactly two sources A and B, adding a directed edge from any node in A to any node in B will result in every node in A being a "root" node in the final graph.

A source is a node that has no incoming edges.

You can compute the SCC graph in O(|V| + |E|) time using Tarjan's SCC algorithm. So the overall complexity is O(|V| + |E|).