Strongly connected components

Maximal groups of directed-graph nodes that all reach each other (and back). Collapse each → the whole graph becomes a DAG.

Kosaraju: two passes + one trick

• Reversing every edge keeps SCCs but flips links BETWEEN them
• Pass 1: DFS the graph, record finish order
• Pass 2: DFS the REVERSED graph in reverse finish order
• Each tree of pass 2 = one SCC. O(V+E).

Watch the components reveal

Grey edges between colors are one-way — you can't get back → separate components. {0,1,2} · {3,4} · {5,6,7}, then collapse to a DAG.

The giant SCC emerges

A phase transition at degree ≈ 1: 0.2% → 89% of nodes in one component by degree 3. (This is the web's "core.")

Kosaraju vs Tarjan

• Kosaraju: two passes, easiest to understand
• Tarjan: one pass, low-link numbers, what libraries use
• Same decomposition — cross-check one against the other
• Undirected graph? Use plain connected components instead

Takeaway

Finish-order reasoning (topological sort) applied to a CYCLIC graph via the transpose. Deadlocks, 2-SAT, compiler loops, the web's bow-tie — all SCCs. Graph tier done. Next tier: strings, starting with KMP.