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.