Tarjan's SCC algorithm
/ TAR-jun /
Tarjan's algorithm finds all strongly connected components of a directed graph in a single depth-first search — no edge reversal, no second pass. It is the more economical sibling of Kosaraju's method, and the trick at its heart is a clever bookkeeping number, the low-link, that lets each vertex figure out, during the one traversal, whether it is the 'top' of an SCC.
Run one DFS, assigning each vertex an index in the order it is discovered, and keep a stack of vertices seen but not yet committed to a component. For each vertex u, maintain low(u): the smallest discovery index reachable from u using tree edges followed by at most one back/cross edge into a vertex still on the stack. You compute it as you return from recursion: low(u) starts at u's own index, and is lowered to low(v) for each tree-child v, and to the index of any already-stacked neighbour w. The pivotal moment: after exploring all of u's edges, if low(u) still equals u's own index, then u cannot reach any earlier-discovered vertex that is still pending — so u is the root of an SCC. You then pop the stack down to and including u, and those popped vertices are exactly one strongly connected component. The intuition: low(u) = index(u) means no back route escapes upward out of the subtree rooted at u into the unfinished part, which is precisely the condition for u to head a maximal mutually-reachable block.
Tarjan runs in O(n + m) with a single traversal and only O(n) extra space for the index, low-link, and stack — strictly leaner in passes than Kosaraju, though both share the same asymptotic cost. It is the go-to in competitive programming and production code where one pass matters. The same low-link idea, applied to undirected graphs, also yields articulation points and bridges, so learning it here pays off three times over. The honest caveat: the low-link bookkeeping is fiddly and easy to get subtly wrong (which neighbours update low, the on-stack check, the pop condition), so it rewards careful implementation; if you just need correctness and clarity over speed of coding, Kosaraju's two-DFS approach is easier to get right.
Graph a->b, b->c, c->a, c->d. DFS indexes a=0,b=1,c=2,d=3. From c the back edge c->a (a on stack) pulls low(c) to 0; that propagates so low(c)=low(b)=low(a)=0. Vertex d has low(d)=3=index(d), so d pops alone: SCC {d}. Back at a, low(a)=0=index(a): pop c,b,a as SCC {a,b,c}.
When low(u) equals u's own index, no escape route reaches an earlier pending vertex, so u roots an SCC and the stack pops it off.
low(u) must track the lowest index reachable through stack vertices only (skip neighbours already committed to a finished SCC). Forgetting the on-stack check is the classic bug that merges components that should stay separate.