Finding all the roots in a directed graph

Question

I need to find an algorithm for finding all the roots in a directed graph, in O(n+m).

I have an algorithm for finding a single root:

1. Run DFS(v) on some v in V. If the result is a single spanning tree, then v is a root. Otherwise, the result is a forest of trees. Then:
2. Run DFS(u) on the root of the last tree. If the result is a single spanning tree, then u is a root. Else, there are no roots in the graph.

Now if I want to find all the roots, is the best way to just run the above algorithm O(n) times, on a different vertex in the last tree every time ? Assuming I found a root, if another root exists then it must be on the last tree, then is it O(n+m) if I continue to run the above algorithm until receiving "no root exists" or until going over all vertices ?

Thanks in advance !

Answer 1

Two approaches:

1. Reverse the graph and calculate DFS-loop() and note the vertices which have no outgoing edges (like Abhishek said).

2. More efficient - Run DFS-loop() on the graph and keep track of vertices with no incoming edges using a true, false table.

Method 1 takes twice as long in the worst case.

Answer 2

First you should find all strongly connected components in graph. To build it in leaner time you can use Kosaraju's algorithm or Tarjan's algorithm. All root should be located in one such component. Next you find strongly connected components without incoming edges to it. If you have more then one such component, graph has no root vertices. In you has only one component, you should check that you can reach others component from it, in this case this components contains all root in graph.

Old variant.

You should calculate the number of incoming edges to vertex, this can be done in O(m). All vertices with zero number of incoming edges will be a root of the graph, for this you will need O(n) time.