One pass components
A strongly connected component is a maximal set of nodes where each can reach every other. Tarjan's algorithm finds all of them in a single depth first search using two numbers per node.
Index and low link
Each node gets a discovery index in the order it is first visited. It also gets a low link, the smallest index reachable from it using tree edges and at most one back edge into nodes still on the stack. As the search unwinds, a node whose low link equals its own index is the root of a component.
- Push each visited node onto a stack.
- Update low link from children and from back edges to stacked nodes.
- When low link equals index, pop the stack down to that node to form one component.
The stack holds nodes that might still belong to the current component, which is what makes a single traversal sufficient.
Key idea
Tarjan finds strongly connected components in one depth first pass by comparing each node's low link to its discovery index, popping a component whenever a node turns out to be a component root.