Tarjan's Strongly Connected Components

A strongly connected component (SCC) of a directed graph is a maximal set of vertices where every vertex can reach every other. Tarjan's algorithm finds all SCCs in a single depth-first search — a classic that shows up whenever a problem asks "which nodes are mutually reachable?"

The slow way first

The brute-force definition is literal: for every pair of vertices, run a reachability check both ways and group the ones that reach each other. Each reachability test is a full traversal, so this is O(V³) or worse — hopeless for a large graph.

The question to ask: while I am exploring with DFS, can I detect a whole component the moment I finish exploring it? Tarjan answers yes, with two small integers per vertex.

The idea: disc and low

Run one DFS. As we first reach a vertex, stamp it with a discovery time disc (a counter that only goes up) and a low-link low, initially equal to disc. low[u] tracks the smallest disc reachable from u using tree edges and at most one back edge to a vertex still on the DFS stack.

We also keep a stack of vertices currently being explored. When a vertex u finishes with low[u] == disc[u], it is the root of an SCC — everything pushed on top of it on the stack belongs to that component, so we pop down to u.

The trick is how low is relaxed: a tree edge u → v pulls low[u] down to low[v], and a back edge to a vertex still on the stack pulls low[u] down to that vertex's disc. A cycle therefore drags every vertex on it down to one shared low value — the root.

Walk through it

Step through the animation. DFS dives 0 → 1 → 2. At 2 the edge 2 → 0 is a back edge to a stacked vertex, so low[2] drops to 0. DFS then explores 2 → 3 → 4. 4 and 3 each finish with low == disc and pop as singletons. Back in the cycle, low propagates up to 0, which finishes as a root and pops 2, 1, 0 together.

Pseudocode

t = 0; stack = []; sccs = []
dfs(u):
    disc[u] = low[u] = t; t += 1
    push u on stack; mark u on_stack
    for each edge u -> v:
        if v unvisited:
            dfs(v); low[u] = min(low[u], low[v])
        else if v on_stack:
            low[u] = min(low[u], disc[v])
    if low[u] == disc[u]:                 # u is an SCC root
        pop vertices off stack down to u, collect as one SCC
for each vertex u:
    if u unvisited: dfs(u)

The Python solution

def tarjan(graph):
    disc, low, on_stack = {}, {}, set()
    stack, sccs, t = [], [], 0
    def dfs(u):
        nonlocal t
        disc[u] = low[u] = t; t += 1
        stack.append(u); on_stack.add(u)
        for v in graph[u]:
            if v not in disc:
                dfs(v)
                low[u] = min(low[u], low[v])
            elif v in on_stack:
                low[u] = min(low[u], disc[v])
        if low[u] == disc[u]:
            comp = []
            while True:
                w = stack.pop(); on_stack.discard(w)
                comp.append(w)
                if w == u: break
            sccs.append(comp)
    for u in graph:
        if u not in disc: dfs(u)
    return sccs

• disc records when each vertex was first seen; low is its low-link; on_stack is a fast membership set.
• On entry we stamp disc[u] = low[u] = t and push u onto the stack.
• A tree edge (v not in disc) recurses, then relaxes low[u] with the child's low[v].
• A back edge to a vertex still on_stack relaxes low[u] with disc[v] — never low[v], which would be wrong for cross edges.
• When low[u] == disc[u], u is a root: pop the stack down to and including u to collect exactly one SCC.

Complexity

A single DFS touches every vertex and edge exactly once, so the work is linear in the graph size. The extra space is the recursion stack plus the explicit vertex stack and the disc/low maps — all O(V).

When this pattern shows up

Practice