Lowlink Values: How One DFS Pass Finds Strongly Connected Components

In a directed graph, two vertices are in the same strongly connected component when each reaches the other. Collapsing every component to a single node produces the condensation, which is always acyclic, and computing it is the standard first step for reachability questions that would otherwise be intractable: mutual reachability in the original graph becomes equality of component identifiers in the condensation, and the reachability relation between components is a partial order that can be traversed once.

The classical method uses two depth-first passes over the graph and its transpose. Tarjan’s method uses one pass, no transpose, and one stack, at the cost of an invariant that is easy to state and easy to break: the lowlink value.

The stack and the index

The algorithm numbers vertices in discovery order with a counter that starts at zero, and maintains a stack of vertices that have been discovered but not yet assigned to a component. A boolean per vertex records whether it is currently on that stack.

For each vertex, the algorithm computes a lowlink value: the smallest discovery index reachable from the vertex by a path consisting of tree edges followed by at most one edge into a vertex that is still on the stack. When a vertex’s lowlink equals its own index, no vertex earlier on the stack is reachable from it, so it is the root of a component; the stack is then popped down to and including that vertex, and everything popped forms one component.

def tarjan_scc(adj):
    n = len(adj)
    index = [-1] * n
    low = [0] * n
    on_stack = [False] * n
    stack = []
    comp = [-1] * n
    counter = 0
    ncomp = 0

    def strongconnect(u):
        nonlocal counter, ncomp
        index[u] = low[u] = counter
        counter += 1
        stack.append(u)
        on_stack[u] = True
        for v in adj[u]:
            if index[v] == -1:
                strongconnect(v)
                low[u] = min(low[u], low[v])       # child's reach
            elif on_stack[v]:
                low[u] = min(low[u], index[v])     # back edge into stack
            # else: v is in an already-emitted component; ignore
        if low[u] == index[u]:
            while True:
                w = stack.pop()
                on_stack[w] = False
                comp[w] = ncomp
                if w == u:
                    break
            ncomp += 1

    for s in range(n):
        if index[s] == -1:
            strongconnect(s)
    return comp, ncomp

The two low updates look similar and are not. For a tree edge, the parent inherits the child’s lowlink, because the child’s reachable set is reachable through the parent. For a non-tree edge into a vertex still on the stack, the parent takes the target’s index, not its lowlink — the edge itself reaches that vertex, and nothing further is implied.

Why the index, not the lowlink, on back edges

The asymmetry is where most implementations go wrong. Using low[v] instead of index[v] on a non-tree edge produces components that are too large, because it lets a vertex claim reachability to something its edge does not directly reach.

The reason for the distinction is that a lowlink value summarizes a set of vertices reachable from v by paths that may leave the stack region temporarily and return to it. The edge (u, v) guarantees only that u reaches v. If v’s lowlink points to an earlier vertex w, then u reaches w via v, and the min operation with index[v] already accounts for that, because v’s lowlink will be at most index[w] and the propagation through the tree edge to v’s parent carries it upward. Replacing the index with the lowlink double-counts a reachability that is already being propagated along the tree edge.

The stack test is equally load-bearing. An edge into a vertex that is not on the stack points into a component that has already been closed and emitted. Vertices in such a component have smaller indices than the current vertex, so including them in the lowlink would incorrectly merge a downstream component into an upstream one. Every implementation must therefore check the on-stack flag, and must clear it on pop, or it will merge components across the condensation’s edges.

Why the root test identifies exactly one component

When low[u] == index[u], no vertex below u on the stack is reachable from u. Since the stack holds exactly the vertices discovered but not yet assigned, and vertices are pushed in discovery order, everything above u on the stack is a vertex discovered after u and still pending. The claim is that the set popped down to u is exactly u’s component.

Two inclusions are needed. Every popped vertex reaches u: it was discovered after u and is still on the stack, which means its own component root has not been found yet, and the standard argument shows the stack contents between a root and the top are the root’s component. Every vertex that reaches u and is reachable from u is on the stack at that moment, because if it had been popped already it would belong to a component that finished earlier, and a component that finished earlier cannot reach u without u having been on the stack at that time, which would have prevented it from finishing.

The second half is the subtle one. Components are emitted in reverse topological order of the condensation: when a component is popped, all components it can reach have already been popped. That property is what makes the algorithm’s output directly usable — the component identifiers are numbered in an order such that every edge between distinct components goes from a higher identifier to a lower one, which is a reverse topological numbering of the condensation. Kosaraju’s two-pass method produces the same ordering property by a different mechanism: the second pass runs on the transpose in decreasing finish-time order, and the components emerge in topological order.

One pass against two

Kosaraju’s algorithm runs a depth-first search on the graph to compute finish times, then a second depth-first search on the transpose, taking roots in decreasing finish order. It needs the transpose stored, which doubles edge storage, and it needs finish times from the first pass, which means the iterative formulation must preserve them correctly. In exchange, its correctness argument is simpler: the vertex with the largest finish time in the first pass belongs to a source component of the condensation, and in the transpose that component has no outgoing edges to any other component, so the second pass cannot leave it.

Tarjan’s method needs no transpose and one pass, so it touches each edge once instead of twice and uses one fewer array of size n plus the reverse adjacency. The saving is real on large graphs where the transpose is a significant fraction of memory, and it matters most in the streaming case where the edge list can be read once.

The cost is implementation difficulty. The recursion depth is O(n), and the algorithm is markedly harder to make iterative than plain DFS because the parent’s lowlink update happens after the child returns, so the explicit frame must carry both the edge cursor and a way to propagate the value upward. The natural frame-based translation stores the parent’s lowlink and updates it when a child frame pops:

def tarjan_iterative(adj):
    n = len(adj)
    index = [-1] * n; low = [0] * n
    on_stack = [False] * n; stack = []
    comp = [-1] * n
    counter = 0; ncomp = 0
    frames = []      # [vertex, next_edge, parent]

    for root in range(n):
        if index[root] != -1:
            continue
        index[root] = low[root] = counter; counter += 1
        stack.append(root); on_stack[root] = True
        frames.append([root, 0, -1])
        while frames:
            u, i, parent = frames[-1]
            if i < len(adj[u]):
                v = adj[u][i]
                frames[-1][1] = i + 1
                if index[v] == -1:
                    index[v] = low[v] = counter; counter += 1
                    stack.append(v); on_stack[v] = True
                    frames.append([v, 0, u])
                elif on_stack[v]:
                    low[u] = min(low[u], index[v])
                continue
            frames.pop()
            if parent != -1:
                low[parent] = min(low[parent], low[u])
            if low[u] == index[u]:
                while True:
                    w = stack.pop(); on_stack[w] = False
                    comp[w] = ncomp
                    if w == u:
                        break
                ncomp += 1
    return comp, ncomp

The parent propagation at pop time is the piece that a plain iterative DFS lacks. Omitting it leaves the lowlink updated only by edges examined directly, so a vertex whose route to an earlier discovery index runs through its own descendants is treated as a component root, the stack is cut at the wrong place, and components fragment into pieces. On a DAG every vertex is already its own component, so a test that only checks the component count passes anyway.

Degenerate inputs and the bounds

A graph with no edges has n components of one vertex each; the algorithm returns exactly that, and the stack never holds more than one entry. A single cycle of length n has one component, and the root is the first vertex discovered on the cycle; the lowlink of every other vertex on the cycle equals the root’s index, so nothing pops until the root finishes, at which point the entire stack empties at once. That is the worst case for stack depth, and it coincides with the case that overflows a recursive implementation.

Self-loops are irrelevant to the decomposition: an edge from a vertex to itself satisfies on_stack[v] with index[v] == index[u], and the min operation changes nothing. Parallel edges are likewise harmless, though they cost an extra comparison each.

The running time is Θ(n + m) for the same reason BFS and DFS are: each vertex is pushed and popped once, and each edge is examined once from its tail. Memory is Θ(n) for the index, lowlink, on-stack, and component arrays, plus a stack that can hold n vertices. On a graph with a hundred million vertices the four per-vertex arrays, counted at 4 bytes per slot, come to 1.6 GB before any adjacency structure, which is why large-scale implementations either use 32-bit identifiers throughout or shard the graph and run the algorithm per shard with cross-shard edges handled separately.

The condensation itself is then built by one pass over the edges, emitting an edge between components whenever the endpoints differ, and deduplicating. That pass is linear and is where the answer to the original reachability question becomes a topological ordering problem on an acyclic graph, which the finish-time method handles directly.