Strongly connected components
In a directed graph a strongly connected component or SCC is a maximal set of vertices where every vertex can reach every other by following edge directions. Mutual reachability defines the groups. Collapsing each SCC to a single node turns any directed graph into a directed acyclic graph of components.
Kosaraju's two pass method
One classic algorithm by Kosaraju uses two depth first searches.
- Run DFS on the graph and record vertices in order of finish time, pushing each onto a stack as its recursion completes.
- Reverse every edge in the graph.
- Pop vertices from the stack and run DFS on the reversed graph. Each DFS tree you grow is one SCC.
The finish order ensures you start each reversed search at a vertex whose component cannot leak into others, so each tree captures exactly one component.
Why reversal works
Reversing edges keeps SCC membership the same, because mutual reachability is symmetric under reversal, but it cuts the one way links between different components. That separation is what makes the second pass isolate each group cleanly. Tarjan's algorithm reaches the same result in a single pass using low link values.
Key idea
Kosaraju records DFS finish order, reverses the edges, and runs DFS again so each search tree on the reversed graph is one strongly connected component.