Hi all,

I have a question regarding the Tarjan's algorithm for finding strongly connected components. The Tarjan's algorithm that I am taught for finding strongly connected components is as follows:

1. Start from any arbitrary vertex.
2. DFS from that vertex. For each node x, keep two numbers, dfs_num[x] and dfs_low[x]. dfs_num[x] stores when that node is visited, while dfs_low[x] = min( dfs_low[k]) where k is all the children of x that is not the directly parent of x in the dfs-spanning tree.
3. All nodes with the same dfs_low[x] are in the same strongly connected component.

However, there seems to be a problem. Suppose the following testcase.

6 -> 5 -> 4 -> 3 -> 2 -> 1

Suppose I process the nodes in this order {1, 2, 3, 4, 5, 6}. Then, we notice that all the nodes will have dfs_low value 1, implying that all are in the same strongly connected component. Obviously that is not true.

To solve this problem, I think what needs to be done is that the dfs needs to be started from nodes with no incoming edges ie the nodes that will be the roots of the dfs-spanning tree.

However, that seems to require require much more computation. Firstly, a for loop is needed to find all nodes with no incoming edges. Then, dfs will be run from these nodes. Then, another for loop is needed to find any unvisited nodes (these nodes will be in a cycle) and dfs needs to be run again. In total, the runtime will be something like O(2*V+E).

Of course, essentially only one dfs is run (since the dfs visits different components of the graph). However, I wonder if there is an easier way to solve this problem, so that instead of breaking the dfs into two parts, only a single dfs needs to be run.

Thanks in advance!