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!

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!

Yep you are right. But I was wondering if there is way to do so without running more for loops, as this would seem to waste some time, although the complexity is still the same. However, suppose if E is close to V, it might be that kosaraju is faster! :O

So is there another way without doing the V-loops?

Visiting Node 1: dfs_num[1] = 1; dfs_low[1] = 1 as node 1 has no children

Visiting Node 2: dfs_num[2] = 2; dfs_low[2] = dfs_low[1] = 1 as node 1 is a children of node 2 and is not a direct parent and it has dfs_low value of 1

Visiting Node 3: dfs_num[3] = 3; dfs_low[3] = dfs_low[2] = 1 as node 2 is a children of node 2 and is not a direct parent and it has dfs_low value of 1.

Visiting Node 4: ...

In the end the dfs_low of all the nodes are 1.

This is my code: http://pastebin.com/nvX7DHBv