Gabow's SCC Algorithm, in depth: path-based DFS with two stacks, a correctness argument and an iterative implementation

The path-based idea

Start with a naive approach. Walk a DFS path from a root. Whenever you find an edge from the current vertex back to a vertex already on the path, you have found a cycle, and every vertex on that cycle belongs to the same SCC. So contract the cycle into one super-vertex and keep going. When the DFS finishes a super-vertex and has found no way back to anything earlier, that super-vertex is a complete SCC. This is the path-based idea, and it goes back to work by Purdom and by Munro around 1970. The difficulty is doing the contraction cheaply. Merging sets naively costs more than linear time.

Gabow's contribution is an implementation of the contraction that is linear and very simple. It keeps two stacks alongside the usual preorder numbers:

• S holds every vertex that has been visited but not yet assigned to a component, in the order it was visited. Vertices on S are exactly the vertices of the contracted path, laid out flat.
• P holds boundaries. Each entry is the first vertex, in preorder, of one super-vertex on the current path. The vertices of S between two consecutive boundaries all belong to the same tentative component as the lower boundary.

Contracting a cycle is now just popping P. If the current vertex has an edge to a vertex w that is still on S, then every super-vertex from w's onward lies on a cycle through that edge. Pop every boundary whose preorder number is greater than w's, and the remaining top of P is the boundary of the merged super-vertex. Each vertex is pushed onto P once and popped at most once, so all merging across the whole run costs O(V).

When the DFS finishes a vertex v and v is still the top of P, v is the boundary of a super-vertex that never found an edge back below itself. Pop v off P, then pop S down to and including v. Those vertices form one SCC.

Why it is correct

The algorithm is easy to state, but you should be able to argue why it is right, because the argument is what lets you modify it safely. Hold three invariants while the DFS runs.

1. S is a preorder-sorted list of unassigned visited vertices. Vertices are pushed when first visited and removed only in contiguous blocks from the top, so S is always increasing in preorder.
2. Every block between consecutive boundaries is strongly connected. A block starts as a single vertex. It grows only by merging, and merging happens only when a cycle through all the merged blocks has been seen.
3. The blocks form a path. Each block contains a vertex on the current DFS stack, and each block can reach the next one through tree edges. So for any vertex w on S, there is a path from w to the current vertex.

Now consider an edge v to w found while exploring v. There are three cases. If w is unvisited, the DFS descends and pushes a new block. If w was visited and is already assigned, its SCC is finished, and by the third invariant applied at the time it finished, it has no path back to the current path; the edge can be ignored. If w is visited and still on S, invariant three gives a path from w to v, and the edge closes a cycle. Every block from w's block up to v's block lies on that cycle, so merging them preserves invariant two.

Finally, when v finishes and v is the top boundary, nothing reachable from v's block found an edge into an earlier block; if it had, v would have been popped as part of a merge. Every vertex reachable from the block is either inside it or already assigned to a finished SCC. The block is therefore maximal and is a complete SCC. Because an SCC is emitted only after everything it can reach has been emitted, components come out in reverse topological order of the condensation, the same order Tarjan's produces.

A traced example

Take the graph with edges a to b, b to c, c to a, c to d, d to e, e to d and e to f. Number vertices in preorder as they are visited: a is 0, b is 1, c is 2, d is 3, e is 4 and f is 5. The diagram shows the state of both stacks after each interesting event.

Walk through it. Visiting a, b and c pushes each onto both stacks. At c the edge to a finds a on S with preorder 0, so P pops c and b and is left with just a: the three vertices are now one tentative block. The edge from c to d starts a new block, and so does e. The edge from e back to d pops e, merging d and e. The edge from e to f starts a third block. Vertex f has no outgoing edges, finishes as the top of P, and is emitted alone as SCC 0. Back at e, the top of P is d, not e, so nothing is emitted. When d finishes it is the top, so S pops e and d as SCC 1. When c and b finish they are not boundaries. When a finishes, S pops c, b and a as SCC 2.

Check the order: f was emitted before {d, e}, which was emitted before {a, b, c}. In the condensation, {a, b, c} points to {d, e}, which points to {f}. Components came out sinks first, as promised.

Recursive and iterative implementations

The recursive form is the clearest statement of the algorithm. It is a direct transcription of the rules above.

def gabow_scc_recursive(n, adj):
    pre = [-1] * n          # preorder number, -1 = unvisited
    comp = [-1] * n         # component id, -1 = unassigned
    S, P = [], []
    counter = 0
    ncomp = 0

    def visit(v):
        nonlocal counter, ncomp
        pre[v] = counter
        counter += 1
        S.append(v)
        P.append(v)
        for w in adj[v]:
            if pre[w] == -1:
                visit(w)
            elif comp[w] == -1:              # visited, still on S: contract
                while pre[P[-1]] > pre[w]:
                    P.pop()
        if P[-1] == v:                       # v is a boundary: emit its block
            P.pop()
            while True:
                x = S.pop()
                comp[x] = ncomp
                if x == v:
                    break
            ncomp += 1

    for v in range(n):
        if pre[v] == -1:
            visit(v)
    return ncomp, comp

Do not ship the recursive version for large inputs. A path graph with a million vertices needs a million stack frames, which overflows the default stack in Python, the JVM and most C runtimes. The iterative version keeps an explicit stack of (vertex, next-edge-index) pairs, which is the standard technique described in iterative DFS with an explicit stack.

def gabow_scc(n, adj):
    pre = [-1] * n
    comp = [-1] * n
    S, P = [], []
    counter = ncomp = 0
    for root in range(n):
        if pre[root] != -1:
            continue
        pre[root] = counter; counter += 1
        S.append(root); P.append(root)
        work = [(root, 0)]
        while work:
            v, i = work[-1]
            if i < len(adj[v]):
                work[-1] = (v, i + 1)
                w = adj[v][i]
                if pre[w] == -1:
                    pre[w] = counter; counter += 1
                    S.append(w); P.append(w)
                    work.append((w, 0))
                elif comp[w] == -1:
                    while pre[P[-1]] > pre[w]:
                        P.pop()
                continue
            work.pop()                       # v is finished
            if P[-1] == v:
                P.pop()
                while True:
                    x = S.pop()
                    comp[x] = ncomp
                    if x == v:
                        break
                ncomp += 1
    return ncomp, comp

Two details matter. First, the merge test uses comp[w] == -1 to mean "w is on S". That works because a visited vertex is on S exactly until it is assigned. You do not need a separate on-stack flag, which is one of the small savings over Tarjan's. Second, self-loops need no special case: an edge from v to v compares v's preorder with itself, pops nothing, and leaves v as a boundary.

Gabow, Tarjan and Kosaraju compared

All three are O(V + E) time. The practical differences are constant factors and clarity. Kosaraju's needs the reversed graph, which doubles edge memory unless you already store both directions, and it touches every edge twice. Tarjan's and Gabow's each make one pass. Gabow's replaces the min(low[v], low[w]) updates and the on-stack flag with pops on P. The two one-pass algorithms usually perform similarly, so measure on your own data.

The bigger reason to choose Gabow's is maintainability. The low-link rule in Tarjan's has a classic trap: using low[w] versus index[w] for back edges, and forgetting the on-stack check for cross edges. Both bugs pass small tests. Gabow's invariant, "P holds the first vertex of each contracted block on the path", is simpler to check by eye and to assert in debug builds.

Using the components

Once you have component ids, a few uses follow immediately.

• Condensation. Build a DAG with one node per component and an edge between components whenever an original edge crosses them, deduplicated. Because Gabow's emits components in reverse topological order, component ids already give a topological order of the condensation when read from highest to lowest, so you can run DAG dynamic programming without a separate topological sort.
• 2-SAT. Build the implication graph with two literals per variable. The formula is unsatisfiable exactly when some x and not-x share a component. A satisfying assignment sets x true when x's component comes later in topological order (closer to the sinks) than not-x's; with reverse-topological ids that means when comp[x] < comp[not_x]. The full construction is in 2-SAT.
• Cycle reporting in build and package graphs. Any component with more than one vertex, or a single vertex with a self-loop, is a cycle. Report the component members rather than one arbitrary cycle; users fixing a dependency tangle want the whole set.

Failure modes

These are the bugs and operational problems that show up in real use.

• Merging on edges to assigned vertices. If you forget the comp[w] == -1 check and pop P for any visited w, cross edges into finished components merge unrelated blocks. Small acyclic tests catch this only if they contain a cross edge, so include one.
• Comparing vertex ids instead of preorder numbers. The pop condition must compare pre[P[-1]] > pre[w]. Vertex ids are arbitrary labels, so comparing them works on graphs that happen to be labelled in DFS order and fails everywhere else.
• Stack overflow. Covered above: recursion depth equals the longest DFS path. Use the iterative form.
• Graphs that change while you run. The algorithm assumes a static graph, so run it on a snapshot. Recomputing from scratch is usually fast enough for graphs of millions of edges.

Testing it

Test against an independent implementation, not hand-made expected outputs. Generate random directed graphs, including empty graphs, self-loops, duplicate edges and long chains. Run Gabow's and a reference such as Kosaraju's, then compare the partitions, not the raw ids, because the two number components differently.

Then add one property check: for every edge from u to v, comp[u] >= comp[v] must hold. That tests the reverse-topological output order directly and catches most ordering mistakes.

What to do next

Use this checklist to put Gabow's algorithm to work.

1. Implement the iterative version above in your language, with preallocated integer arrays for S, P and the work stack.
2. Write the randomised differential test against a reference implementation and the edge-order property check.
3. Run it on a graph that matters to you, such as your build dependency graph, and list every non-trivial component.
4. Build the condensation and use the component ids as a topological order for one DAG computation.
5. Benchmark against your existing SCC code on real inputs before replacing it, and keep the faster one.
6. If you need 2-SAT next, reuse the same routine on the implication graph instead of writing a second SCC pass.