Kosaraju–Sharir SCC

Micha Sharir / S. Rao Kosaraju, 1978

Kosaraju’s formulation (often cited with Sharir) runs DFS on the original digraph to build a finishing-time stack, then runs DFS on the transpose graph in that order—each restart finds one strongly connected component. Gold traces the examined arc, pass one uses the forward edges, pass two reverses them, and teal floods vertices once assigned to a component.