Kosaraju’s Algorithm: Finding Strongly Connected Components

April 2026 · 28 min read

In a directed graph, some groups of vertices are so tightly connected that you can reach every vertex in the group from every other vertex in the same group. These groups are called Strongly Connected Components (SCCs). Kosaraju’s Algorithm finds all of them in linear time using two elegant passes of DFS. In this post we will dissect the algorithm, walk through a visual example step by step, build an interactive animation, write production-quality C++ code, and prove why it works.

What Are Strongly Connected Components?

A Strongly Connected Component of a directed graph is a maximal set of vertices such that there is a directed path from every vertex in the set to every other vertex in the set. “Maximal” means you cannot add any more vertex without breaking this property.

Consider this directed graph with 8 nodes. It contains three SCCs, highlighted with dashed outlines:

Within each colored group, you can follow directed edges to get from any node to any other node in the same group. For instance, in the green group: 0→1→2→0 forms a cycle, so every pair is mutually reachable. But node 0 can reach node 3 (via 1→3), while node 3 cannot reach node 0 — so they belong to different SCCs.

Why Do SCCs Matter?

SCCs appear everywhere:

• Web connectivity: Groups of web pages where you can navigate from any page to any other page within the group via hyperlinks.
• Social networks: Clusters of users who can all reach each other through directed follow/friendship chains.
• Compiler optimization: Cycles in function call graphs or dependency graphs represent mutual recursion or circular dependencies.
• 2-SAT problems: The satisfiability of a 2-SAT formula is determined by whether any variable and its negation belong to the same SCC in the implication graph.
• Ecosystem modeling: In food webs, SCCs identify groups of species with mutual predator-prey relationships.

Any time you need to decompose a directed graph into its “tightly connected clusters,” you need an SCC algorithm.

The Set Intersection Approach (Naive)

Before studying Kosaraju’s clever algorithm, let’s understand the most natural way to compute SCCs — the set intersection approach. This builds the core intuition you need.

The Simple Idea

Think about what it means for two nodes to be in the same SCC: they can reach each other. So for any node v, its SCC is simply the set of all nodes that satisfy both conditions:

1. v can reach u — there exists a directed path from v to u in G
2. u can reach v — there exists a directed path from u to v in G

We can find each of these sets independently:

The SCC of v is simply the intersection of these two sets:

Worked Example: Finding SCC(0)

Let’s trace this on our example graph for node 0:

This matches! Nodes 3–7 are reachable from 0, but they cannot reach back to 0, so they’re in different SCCs.

The Algorithm (Pseudocode)

To find all SCCs naively, repeat this process for each unassigned node:

Why This Is Too Slow

For each unassigned node, we run two full DFS traversals. In the worst case (e.g., every node is its own SCC), that’s V nodes × O(V+E) per DFS = O(V × (V+E)) total. For V = 200,000 and E = 500,000, that’s ~140 billion operations — way too slow.

The genius of Kosaraju’s algorithm is that it computes all these intersections simultaneously using just two total DFS passes instead of two per node. The secret ingredient is the finish order from Pass 1, which cleverly batches the work. We’ll see exactly how the two are equivalent after understanding the algorithm.

Prerequisites

Before diving into Kosaraju’s algorithm, make sure you’re comfortable with these concepts:

DFS & Finish Times

Depth-First Search explores a graph by going as deep as possible before backtracking. A critical concept for Kosaraju’s algorithm is the finish time of each node — the moment DFS finishes processing a node (i.e., all its descendants have been fully explored and DFS backtracks from it).

In our example, running DFS from node 0 produces this finish order (earliest to latest): 3, 7, 6, 5, 4, 2, 1, 0. Pushed onto a stack, the top is 0 (latest finish) and the bottom is 3 (earliest finish).

Graph Transpose

The transpose (or reverse) of a directed graph G is a new graph G^T with the same vertices but every edge reversed. If G has edge u→v, then G^T has edge v→u.

Key property: G and G^T have exactly the same SCCs. Reversing all edges doesn’t break the mutual reachability within any SCC — if you could go from u to v and back in G, you can still do so in G^T (the paths just swap directions).

Condensation Graph (DAG of SCCs)

If you collapse each SCC into a single “super-node,” the resulting graph is always a DAG (Directed Acyclic Graph). This is called the condensation of G. It captures the high-level structure of how SCCs connect to each other. We’ll explore this in detail later in the post.

Kosaraju’s Algorithm — The Idea

Kosaraju’s algorithm (also called the Kosaraju-Sharir algorithm) finds all SCCs using two passes of DFS. The key insight is beautifully simple:

Here’s why this works intuitively:

1. Pass 1 discovers the “reachability frontier” of each node. Nodes that finish later in DFS can reach more of the graph. In particular, a node in an SCC that has outgoing cross-SCC edges will finish later than nodes in the “downstream” SCCs.
2. Transposing the graph reverses the direction of cross-SCC edges. So if SCC A had an edge to SCC B in the original graph, now SCC B has an edge to SCC A in the transpose.
3. Pass 2 processes nodes in reverse finish order (latest finish first). Starting DFS from the node with the latest finish time on the transposed graph, DFS can only reach nodes in the same SCC — because cross-SCC edges now point the wrong way (toward already-processed SCCs).

Think of it like this: Pass 1 determines the “pecking order” of SCCs, and Pass 2 uses that order to peel off one SCC at a time, starting from the “source” SCCs of the condensation DAG.

The Three Steps

Kosaraju’s Algorithm — Step-by-Step Animation

Step through Kosaraju’s algorithm to see both DFS passes with color-coded SCCs.

C++ Implementation

Here is a clean, well-commented C++ implementation of Kosaraju’s algorithm:

#include <bits/stdc++.h>
using namespace std;

class KosarajuSCC {
    int V;
    vector<vector<int>> adj;    // original graph
    vector<vector<int>> adj_t;  // transposed graph

    // Pass 1: DFS on original graph, push to stack on finish
    void dfs1(int u, vector<bool>& visited, stack<int>& stk) {
        visited[u] = true;
        for (int v : adj[u]) {
            if (!visited[v])
                dfs1(v, visited, stk);
        }
        stk.push(u);  // push when node finishes
    }

    // Pass 2: DFS on transposed graph, collect component
    void dfs2(int u, vector<bool>& visited, vector<int>& component) {
        visited[u] = true;
        component.push_back(u);
        for (int v : adj_t[u]) {
            if (!visited[v])
                dfs2(v, visited, component);
        }
    }

public:
    KosarajuSCC(int V) : V(V), adj(V), adj_t(V) {}

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj_t[v].push_back(u);  // build transpose simultaneously
    }

    vector<vector<int>> findSCCs() {
        // Step 1: Fill the stack with finish order
        vector<bool> visited(V, false);
        stack<int> stk;
        for (int i = 0; i < V; i++) {
            if (!visited[i])
                dfs1(i, visited, stk);
        }

        // Step 2: Process nodes in reverse finish order on G^T
        fill(visited.begin(), visited.end(), false);
        vector<vector<int>> sccs;

        while (!stk.empty()) {
            int u = stk.top();
            stk.pop();
            if (!visited[u]) {
                vector<int> component;
                dfs2(u, visited, component);
                sccs.push_back(component);
            }
        }
        return sccs;
    }
};

Complexity Analysis

Time Complexity: O(V + E)

Let’s break down each step:

• Pass 1 (DFS on G): Visits every vertex and edge exactly once — O(V + E).
• Transpose: If built simultaneously with the original graph (as in our implementation), this is O(1) extra. If built separately, it’s O(V + E).
• Pass 2 (DFS on G^T): Again visits every vertex and edge exactly once — O(V + E).

Total: O(V + E) — linear in the size of the graph. This is optimal because you need to examine every vertex and edge at least once to determine SCCs.

Space Complexity: O(V + E)

• Adjacency lists for G and G^T: O(V + E) each.
• Visited arrays: O(V).
• Finish stack: O(V).
• Recursion stack (worst case): O(V).

Total: O(V + E).

Why Does It Work? (Correctness Proof Intuition)

The correctness of Kosaraju’s algorithm rests on a key lemma about finish times and the structure of the condensation DAG.

Key Lemma

Proof sketch: Consider an edge u→v where u∈C and v∈C′. During DFS Pass 1, there are two cases:

1. DFS reaches C before C′: DFS from some node in C will eventually cross into C′ via u→v. All of C′ will finish before the DFS in C finishes (since we must backtrack through C after C′ is done). So the last node in C finishes after the last node in C′.
2. DFS reaches C′ before C: Since C′ has no edge back to C (the condensation is a DAG), DFS on C′ cannot enter C. All of C′ finishes before C is even started. Again, max finish time of C > max finish time of C′.

Why Reverse Finish Order on G^T Works

By the lemma, the SCC with the globally highest finish time is a source in the condensation DAG (no SCC has an edge pointing to it). When we start DFS from a node in this source SCC on G^T:

• Within the SCC, all nodes are mutually reachable even in G^T (since SCCs are the same in G and G^T).
• Cross-SCC edges in G^T point into this source SCC, not out of it. So DFS cannot escape to other SCCs.

After this SCC is identified and marked, the next highest-finish-time unvisited node belongs to the next source SCC (in the condensation DAG minus the already-found SCCs). The same argument applies recursively.

This is why the algorithm peels off SCCs one at a time in reverse topological order of the condensation DAG. Each DFS on G^T is perfectly contained within exactly one SCC.

Equivalence to Set Intersection — Why Kosaraju’s Is Preferred

Recall the naive set intersection approach: SCC(v) = R(v) ∩ R^T(v). Kosaraju’s algorithm computes exactly the same intersections, but does so for all nodes simultaneously in linear time. Let’s see why.

What Pass 2 Really Computes

In Pass 2, when we start a DFS from node v on G^T, we find all nodes reachable from v in G^T that haven’t been assigned to an SCC yet. This set is:

The critical insight is that the finish order from Pass 1 guarantees this restricted set is exactly SCC(v). Here’s why:

Side-by-Side Comparison

Why Kosaraju’s Is Preferred Over Naive Intersection

1. Linear time: Two DFS passes = O(V + E) total. The naive approach is O(V²) or worse.
2. No explicit set operations: No hash sets, no intersection computation. The finish order and visited array handle everything implicitly.
3. Simple implementation: Just two DFS passes and a stack. No complex data structures needed.
4. Correctness is elegant: The equivalence to set intersection makes the algorithm easy to reason about and verify.

The Condensation Graph

The condensation of a directed graph G is formed by collapsing each SCC into a single super-node and keeping only the cross-SCC edges (removing duplicates). The result is always a DAG.

For our example graph, the condensation looks like this:

Notice the condensation is a simple chain: SCC 1 → SCC 2 → SCC 3. There are no cycles (by definition of a condensation). The cross-SCC edges 1→3, 2→4 both map to the single edge SCC 1→SCC 2, and edge 4→5 maps to SCC 2→SCC 3.

Why Is the Condensation Useful?

• Simplification: Reduces a complex directed graph to a manageable DAG while preserving high-level connectivity.
• Reachability: Answering “can u reach v?” reduces to checking reachability in the condensation DAG (after identifying which SCCs u and v belong to).
• Topological ordering: The condensation can be topologically sorted, enabling efficient processing of the original graph’s macro-structure.
• 2-SAT: The condensation is directly used to extract the solution once SCCs are found.

Practice Problems

Here are problems to solidify your understanding of SCCs and Kosaraju’s algorithm, ordered from foundational to advanced:

Summary

Let’s recap the key takeaways:

1. Strongly Connected Components are maximal sets of vertices with mutual reachability in directed graphs.
2. The set intersection approach (SCC(v) = R(v) ∩ R^T(v)) is the natural definition but costs O(V × (V+E)).
3. Kosaraju’s Algorithm is an optimized batched version of set intersection that finds all SCCs in O(V + E) using two DFS passes:
   • Pass 1: DFS on G, build finish-order stack
   • Transpose G to get G^T
   • Pass 2: DFS on G^T in reverse finish order
4. The algorithm works because the finish order encodes forward reachability implicitly, and processing in reverse finish order on G^T confines each DFS to exactly one SCC — computing the intersection without explicit set operations.
5. The condensation graph (DAG of SCCs) captures the macro-structure and is useful for reachability queries, 2-SAT, and more.
6. Kosaraju’s runs in O(V + E) time and O(V + E) space (storing both G and G^T).