This algorithm requires a directed graph. Check Settings tab to configure.
Kosaraju's SCC Algorithm
Finds strongly connected components using two DFS passes
Time: O(V + E)
Space: O(V)
Use Case: Web crawling, dependency resolution
Algorithm Execution
Select an algorithm and generate steps to begin visualization
About Kosaraju's SCC Algorithm
Kosaraju's algorithm computes the strongly connected components of a directed graph using two passes of depth-first search, one on the original graph and one on its transpose (all edges reversed). It is conceptually the simplest linear-time SCC algorithm.
How it works
The first DFS records vertices in order of decreasing finish time. The graph is then transposed, and a second DFS processes vertices in that recorded order; each tree grown in the second pass is exactly one strongly connected component. The correctness follows from the fact that reversing edges preserves SCCs but breaks the connections between them. Two linear passes give O(V + E) total time.
Applications
Kosaraju's algorithm serves the same applications as Tarjan's: 2-SAT solvers, compiler analysis, social network community structure, and dependency condensation. Its two-pass structure is easier to explain and implement from scratch, which makes it a popular interview answer when asked to find SCCs.