Strongly connected components
In a directed graph, a strongly connected component is a maximal set of nodes where every node can reach every other. Shrinking each component to a point leaves a graph with no cycles, which is useful for ordering work.
One depth first search
Tarjan's method finds all components in a single depth first search. As it visits nodes it assigns each an increasing index and pushes it onto a stack. For every node it also tracks a low link, the smallest index reachable from that node through the search.
- When exploring an edge to an unvisited node, recurse and update the low link.
- When an edge points to a node still on the stack, update the low link toward that node.
Closing a component
When a node's low link equals its own index, that node is the root of a component. Pop the stack down to that node, and those popped nodes form one strongly connected component. The single pass keeps the whole algorithm linear in nodes and edges.
Key idea
Track an index and a low link during one depth first search, and pop a component whenever a node's low link equals its own index.