TARJAN'S SCC every cycle-cluster in one depth-first pass
A strongly connected component is a maximal set of nodes that can all reach each other. Tarjan finds every one of them in a single depth-first traversal — no second pass — by tracking, for each node, the oldest node its subtree can climb back to. That number is the lowlink, and it is the whole trick.
THE TECHNIQUE index, lowlink, and a stack
DFS the graph, stamping each node with an increasing index as it is first seen and pushing it on a stack. Each node’s lowlink starts at its own index and is lowered to the smallest index still-on-the-stack that its subtree can reach. When a node finishes with lowlink == index, it is the root of an SCC — pop the stack down to it. Run it; each component gets its own colour. live demo
HISTORY & CREDIT the chronology is usually told backwards
Many assume the two-pass “Kosaraju” method is the original and Tarjan the later trick — it is the reverse. Tarjan published in 1972; Kosaraju’s method was unpublished, dated later. cited
19th c. · Charles Trémaux gives depth-first search as a maze-walking rule — Tarjan did not invent DFS; he and Hopcroft turned it into a linear-time algorithmic tool. 1970–71 · Purdom and Munro already extract strong components with DFS — before Tarjan. 1972 · Robert Tarjan (“Depth-first search and linear graph algorithms”) gives the single-pass lowlink — his genuine first: SCCs in one DFS with one auxiliary stack, O(V+E). the fine print · lowlink is the smallest index of a node still on the stack reachable through the subtree plus at most one back/cross edge — a definition textbooks routinely mis-state.
“Tarjan’s algorithm” is ambiguous — he also owns biconnected components, offline LCA, Fibonacci heaps, link-cut trees. single-pass lowlink, 1972
RECOMMEND FOR I-13 the traversal runs; the in-place stack is the friction
Recursion is I-13’s home turf and the graph rides on bounded arrays — here the whole vertex set is reached over an edge list:
$ i13 run scc.i13 # 5 nodes, edges 0-1-2-0, 2-3, 3-4-3
total = 5 # graph machinery runs on arrays; SCCs {0,1,2} and {3,4}
Recommend: the DFS and the index[], lowlink[], onStack[] arrays are exactly what I-13 executes; the grounded run above walks the edge list over arrays. The friction is Tarjan’s in-place shared stack and lowlink minimisation — value semantics (no aliasing) turns that into threading one state array through every return (the node-arena pattern). It runs that way, but a genuine tuple return would make it natural — a fresh, sharp nudge toward multiple-return, the sole withheld frontier (045/048/052/055/059). Note: unlike a heap embedded in an array (062), a DFS stack that also carries per-node lowlink is state the single-return model must carry by hand.