Strongly Connected Components: Kosaraju's Two-Pass Algorithm

In an undirected graph, "connected" is simple: if you can walk from a to b, you can walk back. In a directed graph it is not, and the useful question becomes which nodes can all reach each other. Those groups are the strongly connected components, and Kosaraju's algorithm finds every one of them with two depth-first searches and one reversal. The algorithm is short; the interesting part is explaining why the second pass never spills from one group into the next.

The problem it solves

A strongly connected component (SCC) is a maximal set of nodes where every node can reach every other node along directed edges. Every node belongs to exactly one, even if only itself. The grouping answers practical questions:

• Dependency rings. Services or modules that call each other in a cycle must be deployed, tested and failed over together.
• Cycle reports. A component with more than one node contains a cycle.
• Simplifying a graph. Collapse each component into one node and the result, the condensation, is always a DAG, so topological sort and DAG dynamic programming apply to any directed graph.

A brute force computes, for every node, the set it can reach, and groups nodes that reach each other. That is O(V · (V + E)). Kosaraju does it in O(V + E).

The intuition

Pass one is an ordinary DFS over the whole graph that records the order in which nodes finish, meaning all their descendants are done. The key property: if there is an edge from component X to component Y, then some node of X finishes after every node of Y. Whoever finishes last therefore sits in a source component, one that nothing else leads into.

Reverse every edge. Components do not change, because inside a component every pair has paths in both directions, and reversing all edges keeps that true. But the edges between components now point the other way, so the source component becomes a sink: nothing leads out of it.

Pass two runs DFS on the reversed graph, starting from the last finisher. It sits in a sink of the reversed graph, so the search collects exactly its component and cannot leak out. Mark those nodes, take the highest finisher not yet marked, and repeat. Each restart collects one component.

Watch it run

The animation uses five services, all one-way calls: a, b and c ring each other, and d and e ring each other, though the list of calls does not say so. Pass one is an ordinary DFS: enter a and keep going while there is anywhere to go, through b, c, d and e. e is finished first, number 1 onto the pile, then d, c, b and a; the last finisher will start pass two. Now every arrow turns around. The groups are unchanged, since inside a ring both directions exist, but the one-way road from c to d now points the other way. Pass two starts at a, the highest finisher left, and takes everything reachable backwards: [a, b, c], one restart and one component. Then it starts at d and collects [d, e]. Two groups: each ring deploys together, and the one thing joining them is a one-way call. Reverse the arrows and that call stops being a way in, which is exactly why each restart in pass two cannot leak into the group next door.

The code

The lesson's algorithm as one function, returning the groups and the finishing order:

def kosaraju(g):
    order, seen = [], set()

    def walk(n):                          # pass one: plain DFS
        seen.add(n)
        for m in g[n]:
            if m not in seen:
                walk(m)
        order.append(n)                   # finished: onto the pile

    for n in g:
        if n not in seen:
            walk(n)

    rev = {n: [] for n in g}
    for n in g:
        for m in g[n]:
            rev[m].append(n)              # every arrow turned around

    seen, groups = set(), []

    def collect(n, group):                # pass two: DFS on the reversed graph
        seen.add(n)
        group.append(n)
        for m in rev[n]:
            if m not in seen:
                collect(m, group)

    for n in reversed(order):             # last finisher first
        if n not in seen:
            group = []
            collect(n, group)
            groups.append(sorted(group))
    return groups, order

g = {"a": ["b"], "b": ["c"], "c": ["a", "d"], "d": ["e"], "e": ["d"]}
groups, order = kosaraju(g)
print(order)     # ['e', 'd', 'c', 'b', 'a']
print(groups)    # [['a', 'b', 'c'], ['d', 'e']]

The condensation: one node per component and only the edges between components. Kosaraju emits components in topological order of this DAG, a useful by-product:

def condense(g, groups):
    comp = {n: i for i, grp in enumerate(groups) for n in grp}
    return sorted({(comp[n], comp[m]) for n in g for m in g[n] if comp[n] != comp[m]})

print(condense(g, groups))   # [(0, 1)]   one arrow between the rings

The common alternative, Tarjan's algorithm, needs one DFS and no reversed graph. Each node gets a discovery index and a "low link", the smallest index reachable from its subtree through nodes still on the stack; a node whose low link equals its own index is the root of a component, and everything above it on the stack is popped as one group. It emits components in reverse topological order:

def tarjan(g):
    index, low, on_stack, stack, groups = {}, {}, set(), [], []

    def visit(n):
        index[n] = low[n] = len(index)
        stack.append(n)
        on_stack.add(n)
        for m in g[n]:
            if m not in index:
                visit(m)
                low[n] = min(low[n], low[m])
            elif m in on_stack:
                low[n] = min(low[n], index[m])
        if low[n] == index[n]:            # n is the root of a component
            group = []
            while True:
                m = stack.pop()
                on_stack.discard(m)
                group.append(m)
                if m == n:
                    break
            groups.append(sorted(group))

    for n in g:
        if n not in index:
            visit(n)
    return groups

print(tarjan(g))   # [['d', 'e'], ['a', 'b', 'c']]

Both against a brute force that computes every node's reachable set and groups mutual reachability, on 2,000 random directed graphs, plus a check that Kosaraju's groups come out in topological order:

import random

def reach(g, s):
    seen, todo = {s}, [s]
    while todo:
        for m in g[todo.pop()]:
            if m not in seen:
                seen.add(m)
                todo.append(m)
    return seen

def brute(g):
    r = {n: reach(g, n) for n in g}       # every node's reachable set
    return sorted({tuple(sorted(m for m in g if m in r[n] and n in r[m])) for n in g})

random.seed(21)
ok = True
for _ in range(2000):
    nodes = list(range(random.randint(1, 10)))
    g = {n: [m for m in nodes if random.random() < 0.2] for n in nodes}
    want = brute(g)
    got, _ = kosaraju(g)
    ok &= sorted(map(tuple, got)) == want == sorted(map(tuple, tarjan(g)))
    ok &= all(i < j for i, j in condense(g, got))   # groups come out in topological order
print(ok)          # True

The complexity

• Kosaraju: O(V + E) time: two DFS passes plus building the reversed graph. O(V + E) extra space for the reversed adjacency lists.
• Tarjan: O(V + E) time in a single pass, with O(V) extra space and no reversed copy.
• Brute force: O(V · (V + E)), one search per node. Fine for tiny graphs, and the right way to test the fast ones. The Big-O cheat sheet lists SCCs with the other graph algorithms.

Where it goes wrong

• Running pass two on the original graph. Without the reversal, the search from a source component flows downstream and swallows other components.
• Using start order instead of finish order. The proof depends on finishing times; the order nodes are first entered proves nothing.
• Recursion depth. Both algorithms recurse as deep as the longest path. In Python a long chain needs an iterative DFS with an explicit stack.
• Confusing SCCs with weakly connected components. Ignoring direction and running union-find gives weak components; a to b without a way back is one weak component but two strong ones.
• Forgetting single nodes. A node on no cycle is still its own component.

When it shows up in interviews

It appears as "find the groups of mutually dependent services", "which accounts can all pay each other", or as the hidden step in problems that need a DAG from a graph with cycles. It follows naturally from detecting a cycle in a directed graph and leads into topological sort, which applies to the condensation. For the undirected version, see number of connected components.

How to say it in an interview

"A strongly connected component is a maximal set of nodes that can all reach each other. I would use Kosaraju: one DFS records finishing order; then I reverse every edge, which keeps the components but flips the edges between them; then I run DFS on the reversed graph in decreasing finishing order. The last finisher lies in a source component, which becomes a sink after reversal, so each search collects exactly one component. It is O(V + E). Tarjan's algorithm does it in one pass with low-link values. Collapsing the components gives a DAG, so topological sort applies afterwards."