Gabow's SCC Algorithm

Purpose: Find strongly connected components in $O(V+E)$ with a single DFS pass and two stacks — no low array, no depth bookkeeping. Also called the path-based strong component algorithm.

Algorithm

Maintain two stacks:

• S — every vertex reached and not yet assigned to a component (the same role as Tarjan’s stack);
• P — the “path stack”: vertices that are candidate roots of the component currently being built.

For each unvisited vertex, run dfs(v):

1. Assign preorder[v] the next counter value; push v onto both S and P.
2. For each edge $v\to w$:
   • if w is unvisited → recurse;
   • else if w is not yet assigned to a component → pop from P while preorder[P.top()] > preorder[w]. This merges everything on the current path back to w into one component-in-progress.
3. When v finishes: if P.top() == v, then v is the root of a component — pop vertices off S down to and including v, assign them all a new component id, and pop v from P.

Code

int n, timer_ = 0, ncomp = 0;
vector<vector<int>> adj;
vector<int> pre, comp, S, P;
 
void dfs(int v) {
    pre[v] = timer_++;
    S.push_back(v);
    P.push_back(v);
    for (int w : adj[v]) {
        if (pre[w] == -1) dfs(w);
        else if (comp[w] == -1)
            while (pre[P.back()] > pre[w]) P.pop_back();
    }
    if (P.back() == v) {
        P.pop_back();
        int u;
        do { u = S.back(); S.pop_back(); comp[u] = ncomp; } while (u != v);
        ncomp++;
    }
}
 
void scc() {
    pre.assign(n, -1); comp.assign(n, -1);
    S.clear(); P.clear(); timer_ = ncomp = 0;
    for (int v = 0; v < n; v++) if (pre[v] == -1) dfs(v);
}

Paradigm

Depth-first search with an auxiliary invariant. Gabow’s P stack encodes exactly the information Tarjan stores in low[], but as a structure rather than a number — which is why the code is shorter and slightly faster in practice.

Complexity

• Time: $O(V+E)$ — one DFS, and each vertex is pushed and popped from each stack at most once
• Space: $O(V)$

Correctness Sketch

Invariant: at any point, P holds one representative per strongly connected component so far discovered on the current DFS path, in increasing preorder. When a back or cross edge reaches a vertex $w$ still on S, everything on the path from $w$ to $v$ lies on a cycle through $w$ and $v$, hence in one SCC — popping P down to $w$‘s representative records that merge. When v finishes and is still its own representative, no edge out of $v$‘s subtree reached above $v$, so $v$ is the root of a maximal SCC, and exactly the vertices above $v$ on S belong to it. ∎

Comparison

Algorithm	Passes	Extra arrays	Notes
Kosaraju	2 DFS + reverse graph	order, visited	easiest to remember, needs $G^T$
Tarjan	1 DFS	disc, low, onStack	most commonly written
Gabow	1 DFS	pre, two stacks	no low, marginally faster

All three emit components in reverse topological order of the condensation, which is what makes them useful for 2-SAT.

Variants / Use Cases

• 2-SAT — $x$ is true iff comp[x] > comp[¬x] with these component numberings
• Condensation — contract SCCs to get a DAG, then run DP on it
• Detecting whether a directed graph is strongly connected — one component
• Iterative version — for $V>10^5$ convert the recursion to an explicit stack to avoid stack overflow