Strongly Connected Components (Kosaraju)

Strongly Connected Components asks: in a directed graph, which groups of vertices can all reach each other? Kosaraju's algorithm answers this with a beautiful trick — two depth-first searches and one reversed graph.

The slow way first

The brute-force definition check is painful: for every pair of vertices (u, v), run a search to see if u reaches v and v reaches u. That is O(V·E) work per pair and O(V²·E) overall — hopeless for a large graph.

The question to ask: is there structure I can exploit so one or two passes suffice? There is. SCCs collapse into a directed acyclic "condensation" graph, and the order vertices finish in a DFS encodes that structure.

The idea: order by finish time, then DFS the transpose

Kosaraju is two passes:

1. Pass 1. DFS the original graph. Each time a vertex is fully explored (finished), push it onto a stack. Vertices that finish last sit on top.
2. Pass 2. Reverse every edge (the transpose). Pop vertices off the stack; for each one not yet assigned, run a DFS on the transpose. Every vertex that DFS reaches is one SCC.

Why it works: in the transpose, edges between different components point "backward", so a DFS started from a top-of-stack vertex can only reach vertices inside its own component — it cannot leak into the next one.

Walk through it

Step through the animation. Pass 1 colors vertices as DFS finishes them and pushes each onto the stack, so the stack ends as [F, E, D, C, B, A] with A on top. Then every edge flips to build the transpose. Pass 2 pops A first and tints {A, B, C}, then pops D for {D, E}, then F alone — three colors, three components.

Pseudocode

visited = empty set, order = empty list
function dfs1(u):
    mark u visited
    for each out-neighbor v of u:
        if v not visited: dfs1(v)
    push u onto order        # finished
 
for each vertex u:
    if u not visited: dfs1(u)
 
rg = graph with every edge reversed
 
seen = empty set
function dfs2(u, root):
    mark u seen, assign u to component "root"
    for each out-neighbor v of u in rg:
        if v not seen: dfs2(v, root)
 
for u in order popped from the top:
    if u not seen: dfs2(u, u)   # new SCC
return the component map

The Python solution

def kosaraju(graph, n):
    visited, order = set(), []
 
    def dfs1(u):
        visited.add(u)
        for v in graph[u]:
            if v not in visited:
                dfs1(v)
        order.append(u)        # finished -> push
 
    for u in range(n):
        if u not in visited:
            dfs1(u)
    rg = transpose(graph)      # reverse edges
 
    comp, seen = {}, set()
    def dfs2(u, root):
        seen.add(u); comp[u] = root
        for v in rg[u]:
            if v not in seen:
                dfs2(v, root)
 
    for u in reversed(order):  # pop the stack
        if u not in seen:
            dfs2(u, u)         # new SCC
    return comp

• dfs1 explores the original graph; line 9 pushes a vertex onto order only after all its out-edges are explored — that is the finish-time stack.
• The driver loop on lines 11-13 restarts DFS on any unvisited vertex, so disconnected pieces are all covered.
• Line 14 builds rg, the transpose, by reversing every edge.
• dfs2 walks the transpose and stamps every reachable vertex with the same root.
• Line 23 iterates the finish stack top first (reversed(order)); each fresh root on line 25 starts exactly one new SCC.

Complexity

Both DFS passes touch every vertex and edge once, and building the transpose is also linear. The extra space holds the transpose plus the recursion stack and bookkeeping sets.

When this pattern shows up

Practice