One pass, two numbers
Tarjan's algorithm finds all strongly connected components in a single depth first search. As it visits each node it assigns an index, the order of discovery, and tracks a low link, the smallest index reachable from that node through the current search, including via one back edge.
The active stack
Visited nodes are pushed onto a stack and stay there while they might still belong to an unfinished component. When a node finishes and its low link still equals its own index, that node is the root of a component. Everything sitting above it on the stack, down to and including it, is popped off as one complete SCC.
How low link spreads
- On a tree edge to an unvisited child, recurse, then take the minimum of your low link and the child low link.
- On an edge to a node still on the stack, take the minimum of your low link and that node index.
- Ignore edges to nodes already assigned to a finished component.
Why it is elegant
Because it needs only one traversal and no edge reversal, it visits each node and edge a constant number of times. The low link comparison cleverly detects when a back edge closes a cycle, marking the boundary of a component.
Key idea
Tarjan's algorithm uses a discovery index and a low link on a single depth first search, popping a component whenever a node's low link equals its own index.