Graph Theory37 sections · 1633 units
Open in Course

Tarjan's Algorithm - Intuition

(Single DFS with low-link)

Tarjan's algorithm finds all SCCs in a single DFS pass using discovery times and low-link values. For each node vv, track two values: disc[v] (when vv was first discovered) and low[v] (the lowest discovery time reachable from vv's subtree, including back edges).

When low[v] = disc[v], node vv is the root of an SCC. At this point, pop all nodes from the stack until you reach vv. All popped nodes (including vv) form one complete SCC.