Tarjan's strongly connected components algorithm: Difference between revisions

Revision as of 23:38, 18 August 2022

Revision as of 04:11, 12 December 2022

Line 80:

When each node finishes recursing, if its lowlink is still set to its index, then it is the root node of a strongly connected component, formed by all of the nodes above it on the stack. The algorithm pops the stack up to and including the current node, and presents all of these nodes as a strongly connected component.

Note that <code>''v''.lowlink := min(''v''.lowlink, ''w''.index) </code> is the correct way to update <code>''v.lowlink''</code> if <code>''w''</code> is on stack. Because <code>''w''</code> is on the stack already, <code>''(v, w)''</code> is a back-edge in the DFS tree and therefore <code>''w''</code> is not in the subtree of <code>''v''</code>. Because <code>''v.lowlink''</code> takes into account nodes reachable only through the nodes in the subtree of <code>''v''</code> we must stop at <code>''w''</code> and use <code>''w.index''</code> instead of <code>''w.lowlink''</code>.

== Complexity ==