Strongly connected components

What this chapter covers

The graph tier began with depth-first search and a promise that its finish-order reveals deep structure. This closing chapter cashes that promise in full. A strongly connected component of a directed graph is a maximal group of nodes where every node can reach every other and get back — a tightly wound knot of mutual reachability. Find all of them, collapse each to a single point, and any directed graph, however tangled, becomes a directed acyclic graph: all the cycles are hidden inside the components, and what's left between them is one-way and loop-free. That decomposition is the standard first move in analyzing cyclic directed graphs, from deadlock detection to compiler optimization to web-structure analysis. This chapter builds Kosaraju's algorithm — two depth-first passes and one beautiful trick, reversing every edge — verifies it against Tarjan's single-pass rival, and watches a real phenomenon emerge: as random directed edges accumulate, a giant component suddenly crystallizes when the average degree crosses one.

A bit of history

The two standard algorithms bracket a productive era in graph theory. Robert Tarjan published his single-pass, low-link algorithm in 1972, part of the same burst of depth-first-search work (with John Hopcroft) that also produced linear-time planarity testing and biconnectivity — the papers that turned DFS from a traversal into an analytical instrument. Kosaraju's two-pass algorithm has a curious provenance: S. Rao Kosaraju described it in unpublished 1978 lecture notes, and Micha Sharir published essentially the same method in 1981, so it's sometimes the Kosaraju-Sharir algorithm. Tarjan's is faster in constant factors (one pass, not two) and is what libraries like networkx use, but Kosaraju's is the one everyone learns, because its correctness is so transparent: run DFS, reverse the edges, run DFS again in reverse finish order. The reason two such different-looking algorithms exist for the same problem is that strong connectivity is fundamental enough to have been solved independently more than once — the recurring signature, throughout this tier, of a truly foundational problem.

The intuition

Kosaraju's algorithm rests on a single observation: reversing every edge in the graph leaves the strongly connected components unchanged, but flips the one-way roads between them. If nodes $a$ and $b$ can reach each other, they still can after reversal (a round trip reversed is still a round trip). But if component $X$ could reach component $Y$ one-way in the original, then in the reversed graph $Y$ reaches $X$ instead. So the components are invariant, but their "downstream" and "upstream" swap. That's the lever the algorithm pulls.

Here's how it uses it. Pass one: run depth-first search on the original graph and record the order in which nodes finish (all their descendants explored). The crucial fact — the same one behind topological sort — is that the component finishing last is a "source" component in the condensation: nothing upstream of it remains. Pass two: process nodes in reverse finish order (last-finished first) and run depth-first search on the reversed graph. Starting from that source component and following reversed edges, you can reach exactly the nodes of that one component and no further — because the reversed edges to other components point the wrong way to escape. So the first DFS tree in pass two is precisely one SCC. Mark it done, move to the next unfinished node in reverse finish order, and its DFS tree is the next SCC. Each tree of the second search is exactly one strongly connected component. Two linear passes, and the whole cleverness is the reversal.

Complexity: how it scales

Kosaraju's is $O(V + E)$: two depth-first traversals plus building the transpose, each linear, so the whole thing is linear in the size of the graph. Tarjan's is also $O(V+E)$ but does it in a single pass, saving a constant factor. Space is $O(V)$ for the visited markers, the finish stack, and the component assignment (plus $O(V+E)$ to store the transpose). Linear is as good as it can be — you must read every edge. So rather than race the two algorithms on speed, the face-off uses SCC decomposition to reveal something about directed graphs themselves: how the size of the largest strongly connected component behaves as you sprinkle in random directed edges.

The shape is a phase transition, one of the most striking phenomena in random graphs. Below an average out-degree of about one, the largest strongly connected component is negligible — at degree 0.5 it held about 0.2% of the nodes, meaning the graph is essentially all tiny components and no mutual reachability at scale. Right around degree one, a giant component nucleates: by degree 3, a single strongly connected component engulfed nearly 89% of the whole graph. The transition is sharp and it's not a quirk of the algorithm — it's a real property of directed graphs, the directed cousin of the classic giant-component emergence in random graph theory, and it's why the web has one enormous "core" of pages that all reach each other surrounded by tendrils that don't. SCC decomposition is how you measure that structure, and the algorithm computing it is linear.

What it's good at, what it isn't

SCC decomposition is the right first step whenever you have a directed graph that might contain cycles and you want to understand or simplify its structure. It detects cycles (any component with more than one node, or a self-loop, is a cycle) — the basis of deadlock detection in operating systems and databases, where a cycle in the wait-for graph means processes are stuck waiting on each other. It condenses a tangled graph to a DAG, after which you can run the acyclic algorithms — topological sort, DAG shortest paths, dynamic programming — that assume no cycles. Compilers use it to find loops in control-flow and to group mutually recursive functions; it identifies communities in social and web graphs; it solves 2-SAT in linear time (a classic, surprising application). Whenever "who can reach whom, both ways" matters, SCCs are the tool.

Where it doesn't apply is undirected graphs, where "connected components" (a plain BFS/DFS flood, from the graph-representations chapter) is the simpler and correct notion — strong connectivity is a directed concept, born from edges having direction. It also answers a structural question, not a metric one: it tells you which nodes mutually reach each other, not how far apart they are or by what path. And like any whole-graph analysis it needs the graph in hand; it isn't an online algorithm for edges arriving over time (maintaining SCCs under edge insertions is a harder, separate problem).

The data, or the inputs

The face-off sweeps random directed graphs of 500 nodes across increasing average out-degree and measures the fraction of nodes in the largest strongly connected component — revealing the giant-SCC phase transition around degree one. Correctness is cross-checked against Tarjan's independent single-pass algorithm: on hundreds of random digraphs Kosaraju's components must exactly match Tarjan's, every node must land in exactly one component, and the condensation must be acyclic (verified by topologically sorting the super-graph). The animation runs on a small directed graph with three clear components and reveals them one at a time, coloring each as it's found.

Build it, one function at a time

The edge reversal — the trick the whole algorithm turns on:

def transpose(adj, n):
    """The reverse graph: every edge u → v becomes v → u. Kosaraju's second pass runs on this.
    Reversing edges keeps each SCC intact (if a↔b in the original, still a↔b reversed) but
    flips the one-way links BETWEEN components, which is what isolates them."""
    radj = [[] for _ in range(n)]
    for u in range(n):
        for v in adj[u]:
            radj[v].append(u)
    return radj

Kosaraju's two passes: finish-order stack, then DFS the transpose in reverse:

def strongly_connected_components(adj, n):
    """Kosaraju's algorithm. Pass 1: DFS the graph, pushing each node onto a stack when it
    FINISHES (all its descendants done). Pass 2: DFS the transpose, popping nodes off that
    stack (i.e. in reverse finish order); every tree reached in the second search is one SCC.
    O(V+E). Returns a list of components, each a list of node ids. (Iterative DFS so deep
    graphs don't overflow the call stack.)"""
    # --- pass 1: finish-order stack on the original graph ---
    visited = [False] * n
    order = []                                   # nodes in order of finishing
    for s in range(n):
        if visited[s]:
            continue
        stack = [(s, iter(adj[s]))]
        visited[s] = True
        while stack:
            node, it = stack[-1]
            advanced = False
            for w in it:
                if not visited[w]:
                    visited[w] = True
                    stack.append((w, iter(adj[w])))
                    advanced = True
                    break
            if not advanced:
                order.append(node)               # node is finished
                stack.pop()

    # --- pass 2: DFS the transpose in reverse finish order ---
    radj = transpose(adj, n)
    assigned = [False] * n
    components = []
    for s in reversed(order):
        if assigned[s]:
            continue
        comp = []                                # everything reachable here (in the transpose) is one SCC
        stack = [s]
        assigned[s] = True
        while stack:
            u = stack.pop()
            comp.append(u)
            for w in radj[u]:
                if not assigned[w]:
                    assigned[w] = True
                    stack.append(w)
        components.append(sorted(comp))
    return components

And collapsing the components to their acyclic condensation:

def condensation(adj, n, components):
    """Collapse each SCC to a single super-node; the result is always a DAG. Returns the number
    of super-nodes and the edges between them — the acyclic skeleton of the directed graph."""
    comp_id = [0] * n
    for cid, comp in enumerate(components):
        for node in comp:
            comp_id[node] = cid
    dag_edges = set()
    for u in range(n):
        for v in adj[u]:
            if comp_id[u] != comp_id[v]:
                dag_edges.add((comp_id[u], comp_id[v]))
    return len(components), dag_edges

Watch it work

Here's a directed graph with three strongly connected components, revealed one at a time. At the start every node is grey — the question is which of them can mutually reach each other. Then, component by component, the algorithm colors a group: nodes 0, 1, 2 form a green component (they cycle 0→1→2→0, so each reaches the others and back); nodes 3, 4 a blue one (3↔4); nodes 5, 6, 7 a purple one (5→6→7→5). The grey edges between colored groups are one-way — you can go from the green component to the others but never return — which is exactly why they're separate components. Collapse each colored blob to a single super-node and those one-way edges form a DAG: the tangled directed graph, made acyclic:

The complete code

The from-scratch tab is Kosaraju's two-pass algorithm with the transpose and condensation; the library tab is Tarjan's single-pass algorithm — the independent reference Kosaraju is checked against, and what networkx actually uses. Flip between them to compare two linear-time solutions to the same problem.

"""Strongly connected components — the maximal groups of nodes in a DIRECTED graph that can
all reach each other. Within one component you can get from any node to any other and back;
between components, reachability only goes one way. Collapse each component to a single point
and the whole graph becomes a DAG (the "condensation"), which is why SCCs are the standard
first step in analyzing any cyclic directed graph: they find the cycles-of-cycles and reduce
the rest to the acyclic case you already know how to handle.

This is a fitting close to the graph tier because it comes right back to depth-first search,
where the tier began. Kosaraju's algorithm — built here — finds every SCC with just TWO DFS
passes and one strikingly simple trick: run DFS, record the order in which nodes finish, then
run DFS again on the graph with every edge REVERSED, taking nodes in reverse finish order.
Each tree of that second search is exactly one strongly connected component. Two passes over
the graph, O(V+E), and the reversal is the whole idea.
"""


# region: transpose
def transpose(adj, n):
    """The reverse graph: every edge u → v becomes v → u. Kosaraju's second pass runs on this.
    Reversing edges keeps each SCC intact (if a↔b in the original, still a↔b reversed) but
    flips the one-way links BETWEEN components, which is what isolates them."""
    radj = [[] for _ in range(n)]
    for u in range(n):
        for v in adj[u]:
            radj[v].append(u)
    return radj
# endregion


# region: kosaraju
def strongly_connected_components(adj, n):
    """Kosaraju's algorithm. Pass 1: DFS the graph, pushing each node onto a stack when it
    FINISHES (all its descendants done). Pass 2: DFS the transpose, popping nodes off that
    stack (i.e. in reverse finish order); every tree reached in the second search is one SCC.
    O(V+E). Returns a list of components, each a list of node ids. (Iterative DFS so deep
    graphs don't overflow the call stack.)"""
    # --- pass 1: finish-order stack on the original graph ---
    visited = [False] * n
    order = []                                   # nodes in order of finishing
    for s in range(n):
        if visited[s]:
            continue
        stack = [(s, iter(adj[s]))]
        visited[s] = True
        while stack:
            node, it = stack[-1]
            advanced = False
            for w in it:
                if not visited[w]:
                    visited[w] = True
                    stack.append((w, iter(adj[w])))
                    advanced = True
                    break
            if not advanced:
                order.append(node)               # node is finished
                stack.pop()

    # --- pass 2: DFS the transpose in reverse finish order ---
    radj = transpose(adj, n)
    assigned = [False] * n
    components = []
    for s in reversed(order):
        if assigned[s]:
            continue
        comp = []                                # everything reachable here (in the transpose) is one SCC
        stack = [s]
        assigned[s] = True
        while stack:
            u = stack.pop()
            comp.append(u)
            for w in radj[u]:
                if not assigned[w]:
                    assigned[w] = True
                    stack.append(w)
        components.append(sorted(comp))
    return components
# endregion


# region: condensation
def condensation(adj, n, components):
    """Collapse each SCC to a single super-node; the result is always a DAG. Returns the number
    of super-nodes and the edges between them — the acyclic skeleton of the directed graph."""
    comp_id = [0] * n
    for cid, comp in enumerate(components):
        for node in comp:
            comp_id[node] = cid
    dag_edges = set()
    for u in range(n):
        for v in adj[u]:
            if comp_id[u] != comp_id[v]:
                dag_edges.add((comp_id[u], comp_id[v]))
    return len(components), dag_edges
# endregion

"""The library counterpart and the independent reference. In production, strongly connected
components come from networkx:

    import networkx as nx
    list(nx.strongly_connected_components(G))   # a list of node-sets, uses Tarjan's algorithm

networkx uses TARJAN's algorithm — the other classic SCC method, which finds every component
in a SINGLE depth-first pass (Kosaraju needs two) by tracking a "low-link" number per node:
the oldest node reachable from it. When a node's low-link equals its own index, it's the root
of an SCC and the component is popped off a stack. It's cleverer and one pass, but subtler to
get right; Kosaraju's two passes are easier to see. `tarjan_scc` below is that independent
algorithm, the reference the trace generator checks Kosaraju against.
"""
import sys


# region: tarjan
def tarjan_scc(adj, n):
    """Tarjan's single-pass SCC algorithm. Each node gets an index (DFS discovery time) and a
    low-link (the smallest index reachable via its subtree and back-edges). Nodes are pushed on
    a stack as they're visited; when a node's low-link equals its index, it's an SCC root and
    everything above it on the stack forms the component. Independent of Kosaraju's two-pass
    reversal trick, so it's a real cross-check."""
    sys.setrecursionlimit(max(10000, n * 4))
    index_of = [None] * n
    low = [0] * n
    on_stack = [False] * n
    stack = []
    counter = [0]
    components = []

    def dfs(u):
        index_of[u] = low[u] = counter[0]
        counter[0] += 1
        stack.append(u)
        on_stack[u] = True
        for v in adj[u]:
            if index_of[v] is None:
                dfs(v)
                low[u] = min(low[u], low[v])
            elif on_stack[v]:
                low[u] = min(low[u], index_of[v])   # back-edge to a node still on the stack
        if low[u] == index_of[u]:                   # u is the root of an SCC
            comp = []
            while True:
                w = stack.pop()
                on_stack[w] = False
                comp.append(w)
                if w == u:
                    break
            components.append(sorted(comp))

    for s in range(n):
        if index_of[s] is None:
            dfs(s)
    return components
# endregion

Scratch vs library

That two such different algorithms — Kosaraju's two passes with a reversal, Tarjan's one pass with low-link numbers — compute the identical decomposition is the closing lesson of the graph tier, and it echoes the minimum-spanning-tree chapters: a well-defined structure admits multiple correct algorithms, and cross-checking them against each other is the strongest test of correctness. Kosaraju's wins on clarity — its correctness is a short finish-order argument you can hold in your head — while Tarjan's wins on constant factors, a single pass instead of two, which is why libraries choose it. That trade between the algorithm that's easiest to understand and the one that's fastest to run has appeared throughout this tier (Kosaraju vs Tarjan, Prim vs Kruskal, Bellman-Ford vs Dijkstra), and the practical skill is knowing which axis matters for your situation. In production you'd call networkx.strongly_connected_components; building Kosaraju yourself is what makes "reverse the edges and DFS again" a trick you've watched work rather than a recipe you've memorized.

Where you'll actually meet it

SCC decomposition runs across systems software and data analysis. Operating systems and databases detect deadlocks by finding cycles (non-trivial SCCs) in the wait-for graph of processes and locks. Compilers use SCCs to identify loops in control-flow graphs, to group mutually recursive functions for optimization, and in pointer and dataflow analysis. The 2-SAT problem — is a formula of two-literal clauses satisfiable? — is solved in linear time by building an implication graph and checking its SCCs, a famously elegant application. Web-structure studies use SCCs to find the giant "core" of mutually-linked pages (the bow-tie model of the web). Social-network analysis uses them to find tightly-knit groups, and model-checkers use them to find cycles that represent liveness violations. Anywhere a directed graph has cycles that need finding or collapsing, strongly connected components are the tool.

Takeaways

Strongly connected components are the maximal groups of directed-graph nodes that can all mutually reach each other, and finding them decomposes any tangled directed graph into an acyclic condensation of components. Kosaraju's algorithm finds them in two linear depth-first passes — record finish order, then DFS the edge-reversed graph in reverse finish order — with the edge reversal as its whole insight; it's finish-order (topological-sort) reasoning applied to a cyclic graph. The decomposition is linear, verified here against Tarjan's independent single-pass method, and it exposes real structure, like the giant strongly connected component that abruptly emerges when a random directed graph's average degree crosses one.

With this the graph tier closes, having built up from representation and traversal (BFS, DFS) through ordering (topological sort), the shortest-path family (Dijkstra, Bellman-Ford, Floyd-Warshall, A*), minimum spanning trees (Prim, Kruskal), and finally structural decomposition. The next tier turns from graphs to strings — pattern matching and text algorithms — beginning with the elegant way KMP searches for a pattern in a text without ever backing up, which, like so much here, gets its speed from precomputing structure before the main loop begins.