I am stumbled at this part of SCC. I know that 5,6,7 is a strongly connected component. Performing the tarjan Algorithm for SCC starting at no de 5, I get unsatisfied values of low-link at 7.
Graph and DFS tree
let (x,y) ->(id,low-link)
Performing DFS(node 5),(5,5) I reached at node 6(6,6). From node 6 I have two out-adjacent edges one in-adjacent to node 5 and other one in-adjacent to node 7. Suppose choose the other one in-adjacent to node 7, (7,7). From node 7 there is only one out-adjacent edge going to node 6, which is already visited. Therefore I did the low-link update of (7,7) to (7,6). Then I backtrack to node 6 and explore the that out-adjacent edge going to node 5. So updated (6,6) to (6,5).Then again backtracking to node 5.
According Tarjan I should get (5,5),(6,5),(7,5) but I got (5,5),(6,5),(7,6)
Where did I go wrong?
It is not true that the low
value for all nodes in a strongly connected component must be the same. It is only necessary that the first node visited in the DFS traversal of a strongly connected component have id[node] == low[node]
. Any other node in the strongly connected component should have low[node] < id[node]
as it can reach an earlier node through a back edge.
To actually process the strongly connected components, we can push each node onto a stack when it is first encountered in the DFS traversal. Once we identify the first node of a strongly connected component, we can remove all the nodes from the stack up until that node, which forms a strongly connected component.