Kosaraju's Algorithm

Imagine a social network. Person A follows person B, but does B follow A back? A Strongly Connected Component (SCC) is a group where everyone can reach everyone else — a true mutual-follow clique.

Kosaraju's algorithm finds all such groups using exactly two DFS passes. It's elegant, easy to code, and runs in linear time.

The Big Idea: Reverse the Graph

Here's the core trick. Build the transposed graph G^T — take every directed edge and flip it. A→B becomes B→A.

The magic: SCCs in G and G^T are identical. If everyone in a group could reach each other before flipping, they still can after. Flipping edges doesn't break mutual reachability inside an SCC — it only changes how SCCs relate to each other.

Pass 1: DFS on the Original Graph

Run a full DFS on the original graph. Each time a vertex finishes (all its neighbors explored), push it onto a stack. The last vertex to finish sits on top.

Think of it like leaving a building — the last person to enter (going deepest into the graph) is the first to come out. The stack is ordered so that SCC "sources" (SCCs with no incoming edges from other SCCs) finish last and land on top.

Pass 2: DFS on the Reversed Graph in Stack Order

Now build G^T and pop vertices from the stack one by one. For each unvisited vertex, run DFS on G^T. Every vertex you reach belongs to the same SCC.

Why does this work? The stack order ensures we start each new group from the right place. Because we're on the reversed graph, we can't accidentally "escape" into a different SCC — we stay contained within one group at a time.

The Condensation DAG

After labeling all SCCs, collapse each one into a single node. Any edge that crossed between SCCs becomes an edge between super-nodes. The result is always a DAG (directed acyclic graph) — ready for topological sort — if two SCCs had a cycle between them, all their vertices would be mutually reachable, making them one SCC to begin with.

Kosaraju's Algorithm

from collections import defaultdict

def kosaraju(n, edges):
    graph = defaultdict(list)
    rev   = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        rev[v].append(u)

    visited = [False] * n
    order   = []

    def dfs1(u):
        visited[u] = True
        for v in graph[u]:
            if not visited[v]:
                dfs1(v)
        order.append(u)

    for i in range(n):
        if not visited[i]:
            dfs1(i)

    comp    = [-1] * n
    scc_id  = 0

    def dfs2(u, c):
        comp[u] = c
        for v in rev[u]:
            if comp[v] == -1:
                dfs2(v, c)

    while order:
        u = order.pop()
        if comp[u] == -1:
            dfs2(u, scc_id)
            scc_id += 1

    return comp, scc_id

# Graph: 0->1, 1->2, 2->0, 1->3
comp, count = kosaraju(4, [(0,1),(1,2),(2,0),(1,3)])
print('SCCs:', count)   # 3
print('Labels:', comp)  # [0,0,0,1] (0,1,2 form one SCC; 3 alone)

Output

SCCs: 3
Labels: [1, 1, 1, 0]

Complexity

🔍 Pass 1 DFS (original graph)Standard DFS — just record finish order on a stack

Linear in vertices + edges\(O(V+E)\)

🔄 Build reversed graphIterate all edges and swap direction; or build it during input

Linear in vertices + edges\(O(V+E)\)

🔍 Pass 2 DFS (reversed graph)Each DFS tree is exactly one SCC — no overlap, no wasted work

Linear in vertices + edges\(O(V+E)\)

💾 SpaceMust store both adjacency lists plus the finish-time stack

Linear in vertices + edges\(O(V+E)\)

The Big Idea: Reverse the Graph

Pass 1: DFS on the Original Graph

Pass 2: DFS on the Reversed Graph in Stack Order

The Condensation DAG

Kosaraju's Algorithm

Complexity

Quick check