A Strongly Connected Component (SCC) is a group of vertices in a directed graph where every vertex can reach every other vertex by following directed edges. The 2000 "Bowtie Model" study of the web found that around 30% of all indexed pages belong to one giant SCC, with the rest forming clusters that can reach it or be reached from it but not both.

SCCs appear in social network analysis (groups of people who all follow each other), compiler optimization (cycles in function call graphs), and 2-SAT solvers. They are also a common topic in graph interview questions.

Kosaraju's algorithm finds all SCCs in a directed graph with two passes of DFS. It is conceptually simpler than Tarjan's algorithm and a good way to build intuition for how DFS finish times encode the structure of a directed graph.

In an undirected graph, a connected component is a group of vertices where every vertex can reach every other vertex. In a directed graph, edges have direction, so reaching B from A does not guarantee you can get from B back to A.

A Strongly Connected Component (SCC) is a maximal set of vertices such that for every pair of vertices u and v in the set, there is a directed path from u to v AND a directed path from v to u. "Maximal" means you cannot add any more vertices to the set and keep this property.

Consider the following example.

This graph has three SCCs:

C can reach D (through the edge C to D), but D cannot reach C, so C and D belong to different SCCs. Edges between SCCs always go in one direction, which is a property we will exploit later.

Kosaraju's algorithm finds all SCCs in a directed graph in O(V + E) time using two passes of DFS. The algorithm was independently discovered by S. Rao Kosaraju in 1978 and later published by Micha Sharir in 1981.

The algorithm has three steps:

The following walkthrough covers each step using a concrete graph.

The Example Graph

Consider this directed graph with 8 vertices:

The three SCCs are {0, 1, 2}, {3, 4, 5}, and {6, 7}. Here is how Kosaraju's algorithm discovers them.

Step 1: DFS on the Original Graph (Record Finish Order)

Run DFS starting from any unvisited vertex. When a vertex has no more unvisited neighbors (or all recursive calls from it have returned), push it onto a stack.

Suppose we start DFS from vertex 0:

Stack (top to bottom): 0, 1, 2, 3, 4, 5, 6, 7

The vertex that finishes last ends up on top. This is the key piece of information for step 3.

Step 2: Transpose the Graph

Reverse every edge in the original graph. If the original had an edge from u to v, the transposed graph has an edge from v to u.

The edges within each SCC still form a cycle. If A could reach B and B could reach A in the original, the same is true in the transpose. But the edges between SCCs have flipped direction. In the original, SCC {0,1,2} could reach SCC {3,4,5}. In the transpose, SCC {3,4,5} can reach SCC {0,1,2}. This reversal is what makes the second pass work.

Step 3: DFS on the Transposed Graph (In Stack Order)

Pop vertices from the stack and run DFS on the transposed graph, skipping already-visited vertices. Each DFS tree is one SCC.

Pop 0: DFS from 0 on the transposed graph visits 0 to 2 to 1. All three are in one DFS tree. SCC found: {0, 1, 2}.

Pop 1: Already visited. Skip.

Pop 2: Already visited. Skip.

Pop 3: DFS from 3 on the transposed graph visits 3 to 5 to 4. (3 cannot reach 2 because 2 is already visited.) SCC found: {3, 4, 5}.

Pop 4, 5: Already visited. Skip.

Pop 6: DFS from 6 on the transposed graph visits 6 to 7. (6 cannot reach 5 because 5 is already visited.) SCC found: {6, 7}.

Pop 7: Already visited. Skip.

Result: three SCCs, exactly as expected.

The three steps are easy to follow mechanically. The reason they work is that finish order plus the transpose together guarantee one SCC per DFS call in the second pass.

Finish Order Encodes SCC Structure

When DFS finishes exploring a vertex, it means all vertices reachable from that vertex have already been explored. This means a vertex in an "upstream" SCC (one that can reach other SCCs) will finish after vertices in "downstream" SCCs.

In our example, vertices in SCC {0,1,2} finish after vertices in SCC {3,4,5}, which finish after vertices in SCC {6,7}. So the stack has the "source" SCCs on top.

The Transpose Reverses Inter-SCC Edges

Within an SCC, reversing edges does not change reachability. If u can reach v and v can reach u, the same holds after reversal.

But between SCCs, the direction flips. In the original graph, SCC-A reaches SCC-B. In the transpose, SCC-B reaches SCC-A.

Combining the Two

When we process the stack in step 3, we start with a vertex from a "source" SCC in the original graph. In the transposed graph, this SCC becomes a "sink" (no outgoing inter-SCC edges). So DFS from this vertex explores only vertices within its own SCC, because there are no outgoing edges to other SCCs in the transpose.

Once that SCC is fully marked as visited, we move to the next vertex in the stack. The same logic applies: the DFS can only reach vertices within its own SCC because (a) inter-SCC edges now point inward (not outward) and (b) any SCC that could be reached has already been visited.

This is why the algorithm works: the finish order plus the transpose together ensure that each DFS in step 3 is perfectly contained within one SCC.

Here is the complete implementation of Kosaraju's algorithm.

Output:

The time complexity is O(V + E). We do two DFS passes, each taking O(V + E), and building the transpose takes O(V + E). The space complexity is O(V + E) for the transposed graph, the visited array, and the stack.

SCCs show up in several practical problems and graph interview questions.

1. Condensation Graph (DAG of SCCs)

Once you find all SCCs, you can collapse each SCC into a single vertex. The resulting graph is guaranteed to be a DAG. This condensation is useful for:

2. 2-SAT (Boolean Satisfiability)

The 2-SAT problem asks: given a boolean formula where each clause has exactly two literals, is there a satisfying assignment? This can be modeled as an implication graph, and the formula is satisfiable if and only if no variable and its negation are in the same SCC. Kosaraju's algorithm gives you an O(V + E) solution to 2-SAT.

3. Social Network Analysis

In a follow/friend graph, SCCs represent communities where every member can reach every other member through a chain of follows. Finding these communities helps with recommendation systems and influence analysis.

4. Compiler Optimization

In a function call graph, SCCs represent groups of mutually recursive functions. The compiler can optimize these groups differently from non-recursive functions, for example by applying special inlining or tail-call strategies.

Time Complexity

The overall time complexity is O(V + E). The first DFS pass over the original graph visits every vertex and edge once, which costs O(V + E). Building the transposed graph reverses each edge exactly once, adding another O(V + E). The second DFS pass over the transpose again touches every vertex and edge once for O(V + E). These three phases run one after another rather than nested, so their costs add up to O(V + E).

Space Complexity

The space complexity is O(V + E). The transposed graph holds all V vertices and E edges, which dominates the usage. On top of that, the algorithm keeps a visited array and a finish-order stack, each holding at most V entries, for O(V) additional space.