KOSARAJU-SHARIR two passes, and the transpose graph
Strongly-connected components in two DFS passes: run a DFS and push each vertex when it finishes; then reverse every edge and DFS the transpose in decreasing finish order — each tree the second search grows is exactly one SCC. The whole correctness is one line: a and b are mutually reachable in a graph iff they are in its transpose, so the two share identical components.
THE TECHNIQUE finish order, then DFS the transpose
Digraph on 5 vertices: 0→1→2→0 (a 3-cycle), 2→3, 3→4→3 (a 2-cycle). Pass 1: forward DFS, push on finish. Pass 2: reverse the edges, DFS in that order — each tree is one SCC. Watch the two passes colour the components. live demo
HISTORY & CREDIT simplest to teach, not first, not fastest
“Two-pass came first” — no; Tarjan’s one-pass SCC (1972) predates Kosaraju’s note (1978) by six years. It is the simplest to teach, not the earliest. cited
1972 · Robert Tarjan — the first linear-time SCC, a single DFS with index + lowlink (dart 079). 1976 · Dijkstra’s path-based (stack-of-stacks) single-pass SCC — another one-pass lineage. 1978 / 1981 · S. Rao Kosaraju writes the two-pass transpose method in an unpublished note; Micha Sharirindependently discovers and publishes it (1981, for data-flow analysis). 1983 · Aho-Hopcroft-Ullman print it and credit both — fixing the name “Kosaraju-Sharir.” (Sharir is 1981 not 1979; the nearby 1979 date is Aspvall-Plass-Tarjan’s 2-SAT, which merely uses SCCs.)
Neither invented DFS (that is Tremaux, 19th c.); the novelty is the transpose trick + the finish-order start. Two passes do ~double the work — it wins on clarity, not speed. Kosaraju 1978 / Sharir 1981
RECOMMEND FOR I-13 the transpose is free; SCC via mutual reachability
The digraph is two parallel f64 edge arrays, so “reverse every edge” costs nothing; the components come out exact:
$ i13 run kos.i13 # 0->1->2->0, 2->3, 3->4->3 ; adjacency as successor bitmasks
reach(0)=31 (all) reach(3)=24 ({3,4}) mutual(0,1)=1 mutual(0,3)=0 mutual(3,4)=1
SCC count = 2 components = [0,0,0,1,1] (same partition Tarjan gets in one pass)
Recommend: the partition is LIT — encode the digraph as per-vertex successor bitmasks; transitive closure by OR-to-fixpoint gives each vertex’s reach set; two vertices share an SCC iff mutually reachable, and counting the SCC-minimal vertices gives the count (verified reach(0)=31, reach(3)=24, count 2, components [0,0,0,1,1]). The transpose is free — swap the two edge arrays. Note: what runs is the SCC result via mutual reachability; Kosaraju’s two-pass DFS (the efficient O(V+E) method the demo animates) wants a threaded visited-array + a finish stack — expressible by threading value-semantic arrays, the same pattern as the corpus’s other graph darts (Tarjan 079, Dijkstra 055).