Working of Tarjan's algorithm for finding SCC

Revision en3, by Jim_Moriarty_, 2020-05-10 13:18:40
      • This is the code that I have studied for finding SCC and I have several doubts.
Spoiler

//code is from steven and felix book.

Can one node be contained in two SCCs?

5 6

1 4

1 3

2 4

3 4

4 5

5 1

consider this testcase ; 5 is number of nodes and 6 is the number of directed edges. 1 4 means there is an directed edge from 1 to 4.

if I assume that one node is contained in only one SCC then 1->4->5 will be considered or 1->3->4->5 for 1, 4 and 5.

And how we update dfs_low[u] in case of visited node as dfs_low[u]=min(dfs_low[u], dfs_low[v.first]) or as dfs_low[u]=min(dfs_low[u], dfs_num[v.first]). Which one is correct and why ?

Any help would be appreciated.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English Jim_Moriarty_ 2020-05-10 13:20:02 872
en3 English Jim_Moriarty_ 2020-05-10 13:18:40 856
en2 English Jim_Moriarty_ 2020-05-10 07:24:51 76
en1 English Jim_Moriarty_ 2020-05-10 07:22:33 1574 Initial revision (published)