Kosaraju's Algorithm

A two-pass depth-first method for strongly connected components using the graph and its transpose.

Two passes

Kosaraju's algorithm finds strongly connected components in O(V + E) using two depth-first searches. The first DFS on the original graph records vertices in order of finish time. The second DFS runs on the transpose (all edges reversed), processing vertices in decreasing finish-time order; each DFS tree in this pass is exactly one SCC.

Why it works

Kronos motion — materials first

In the condensation DAG, the vertex with the latest finish time belongs to a source SCC. Reversing the edges makes that SCC a sink, so a DFS from it cannot leave the component. Processing vertices by decreasing finish time therefore peels off one SCC at a time without leaking into others.

Structure

python

def kosaraju(n, adj, radj):
    order, seen = [], [False]*n
    def dfs1(u):
        seen[u] = True
        for w in adj[u]:
            if not seen[w]: dfs1(w)
        order.append(u)
    for v in range(n):
        if not seen[v]: dfs1(v)
    comp = [-1]*n
    def dfs2(u, c):
        comp[u] = c
        for w in radj[u]:
            if comp[w] == -1: dfs2(w, c)
    c = 0
    for v in reversed(order):
        if comp[v] == -1:
            dfs2(v, c); c += 1
    return comp

Comparison

Simpler to prove correct than Tarjan's low-link method.
Requires building the transpose graph and two traversals.
Same linear complexity; Tarjan touches each edge once and is usually a bit faster.
The path-based SCC algorithm (Gabow) is a third single-pass alternative.

Uses

Like Tarjan's algorithm, Kosaraju's is used to condense directed graphs, detect cyclic dependencies, and solve 2-SAT. Its two-phase structure also makes it a clear teaching example of how finish-time ordering exposes graph structure.