Tarjan's SCC Algorithm

A Bit of History

This is the third algorithm in this series traced to Robert Tarjan's single, extraordinarily productive 1972 paper "Depth-First Search and Linear Graph Algorithms" — alongside bridges and articulation points, already met in Part 8. All three share the exact same core idea: a low-link value computed during one DFS pass, repurposed slightly differently for each problem. Tarjan's SCC algorithm is arguably the cleverest application of the three, folding an entire two-pass strategy (Kosaraju's, published around the same era) into a single traversal.

Working Principle

Tarjan's algorithm runs one DFS, maintaining for each vertex \(v\) a discovery index \(\text{disc}[v]\) (the order it was first visited) and a low-link value \(\text{low}[v]\) — the smallest discovery index reachable from \(v\)'s subtree using at most one back edge or cross edge to a vertex still "on the stack" (i.e., part of the current SCC search still in progress). A second stack tracks every vertex currently being explored. When a vertex \(v\) finishes and \(\text{low}[v] = \text{disc}[v]\) (meaning nothing in \(v\)'s subtree can reach back above \(v\)), \(v\) is the root of a complete SCC: pop the stack until \(v\) itself is popped, and every vertex popped along the way belongs to that SCC.

Worked Example

The same graph as the Kosaraju's deep dive: 3-cycle \(A \to B \to C \to A\), 2-cycle \(D \to E \to D\), bridge edge \(C \to D\). Starting DFS at \(A\): \(\text{disc}[A]=0\), visit \(B\) (\(\text{disc}=1\)), visit \(C\) (\(\text{disc}=2\)), which has an edge back to \(A\) (still on the stack) — so \(\text{low}[C] = \min(\text{low}[C], \text{disc}[A]) = 0\). \(C\) also visits \(D\) (\(\text{disc}=3\)) and \(E\) (\(\text{disc}=4\), which links back to \(D\), giving \(\text{low}[E] = \text{low}[D] = 3\)). When \(D\) finishes, \(\text{low}[D] = 3 = \text{disc}[D]\) — pop the stack down to \(D\): SCC \(\{D, E\}\) found. Backtracking further, when \(A\) finishes, \(\text{low}[A] = 0 = \text{disc}[A]\) — pop down to \(A\): SCC \(\{A, B, C\}\) found. Same two SCCs as Kosaraju's algorithm found, in a single pass.

Why Low-Link Values Work

The correctness argument mirrors the bridge-finding argument from Part 8, adapted for strong connectivity: \(\text{low}[v] = \text{disc}[v]\) after \(v\)'s subtree is fully explored means no vertex in that subtree has a back or cross edge to any vertex discovered before \(v\) that is still active (on the stack). Combined with the fact that every vertex still on the stack when \(v\) finishes is, by construction, reachable from \(v\) (they were pushed while exploring \(v\)'s subtree) and can reach back to \(v\) (else they wouldn't still be on the stack) — the set popped is exactly the maximal mutually-reachable group rooted at \(v\), which is precisely the definition of an SCC.

Complexity Analysis

A single DFS traversal, with \(O(1)\) amortized work per stack push/pop:

$$\text{Time: } O(V + E) \qquad \text{Space: } O(V)$$

Implementation

from collections import defaultdict

def tarjan_scc(vertices, edges):
    """edges: list of (u, v) directed edges. Returns list of SCCs (each a list of vertices)."""
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)

    index_counter = [0]
    disc = {}
    low = {}
    on_stack = {}
    stack = []
    sccs = []

    def strongconnect(v):
        disc[v] = low[v] = index_counter[0]
        index_counter[0] += 1
        stack.append(v)
        on_stack[v] = True

        for w in adj[v]:
            if w not in disc:
                strongconnect(w)
                low[v] = min(low[v], low[w])
            elif on_stack.get(w):
                low[v] = min(low[v], disc[w])   # back/cross edge to an active vertex

        if low[v] == disc[v]:                    # v is the root of an SCC
            component = []
            while True:
                w = stack.pop()
                on_stack[w] = False
                component.append(w)
                if w == v:
                    break
            sccs.append(component)

    for v in vertices:
        if v not in disc:
            strongconnect(v)

    return sccs

vertices = ["A", "B", "C", "D", "E"]
edges = [("A", "B"), ("B", "C"), ("C", "A"), ("C", "D"), ("D", "E"), ("E", "D")]

print(tarjan_scc(vertices, edges))   # [['D', 'E'], ['A', 'C', 'B']] (order varies)

#include <vector>
#include <unordered_map>
#include <stack>
#include <iostream>
using namespace std;

int indexCounter = 0;
unordered_map<string, int> disc, low;
unordered_map<string, bool> onStack;
vector<string> stk;
vector<vector<string>> sccs;
unordered_map<string, vector<string>> adj;

void strongconnect(const string& v) {
    disc[v] = low[v] = indexCounter++;
    stk.push_back(v);
    onStack[v] = true;

    for (auto& w : adj[v]) {
        if (!disc.count(w)) {
            strongconnect(w);
            low[v] = min(low[v], low[w]);
        } else if (onStack[w]) {
            low[v] = min(low[v], disc[w]);
        }
    }

    if (low[v] == disc[v]) {
        vector<string> component;
        while (true) {
            string w = stk.back(); stk.pop_back();
            onStack[w] = false;
            component.push_back(w);
            if (w == v) break;
        }
        sccs.push_back(component);
    }
}

int main() {
    adj = {{"A", {"B"}}, {"B", {"C"}}, {"C", {"A", "D"}}, {"D", {"E"}}, {"E", {"D"}}};
    vector<string> vertices = {"A", "B", "C", "D", "E"};

    for (auto& v : vertices) if (!disc.count(v)) strongconnect(v);

    cout << "Number of SCCs: " << sccs.size() << endl;  // 2
    return 0;
}

import java.util.*;

class TarjanSCC {
    static int indexCounter = 0;
    static Map<String, Integer> disc = new HashMap<>(), low = new HashMap<>();
    static Map<String, Boolean> onStack = new HashMap<>();
    static Deque<String> stack = new ArrayDeque<>();
    static List<List<String>> sccs = new ArrayList<>();
    static Map<String, List<String>> adj = new HashMap<>();

    static void strongconnect(String v) {
        disc.put(v, indexCounter); low.put(v, indexCounter); indexCounter++;
        stack.push(v);
        onStack.put(v, true);

        for (String w : adj.getOrDefault(v, List.of())) {
            if (!disc.containsKey(w)) {
                strongconnect(w);
                low.put(v, Math.min(low.get(v), low.get(w)));
            } else if (onStack.getOrDefault(w, false)) {
                low.put(v, Math.min(low.get(v), disc.get(w)));
            }
        }

        if (low.get(v).equals(disc.get(v))) {
            List<String> component = new ArrayList<>();
            String w;
            do {
                w = stack.pop();
                onStack.put(w, false);
                component.add(w);
            } while (!w.equals(v));
            sccs.add(component);
        }
    }

    public static void main(String[] args) {
        adj.put("A", List.of("B")); adj.put("B", List.of("C"));
        adj.put("C", List.of("A", "D")); adj.put("D", List.of("E")); adj.put("E", List.of("D"));
        List<String> vertices = List.of("A", "B", "C", "D", "E");

        for (String v : vertices) if (!disc.containsKey(v)) strongconnect(v);

        System.out.println("Number of SCCs: " + sccs.size());  // 2
    }
}

Kosaraju's vs. Tarjan's

Both run in \(O(V+E)\); the practical choice usually comes down to whichever is easier to adapt into a larger codebase — Kosaraju's two clean DFS passes are often preferred for teaching and quick implementation, while Tarjan's single-pass version is preferred in performance-sensitive production code that can't afford to build and store a transpose graph.

Exercises

1. Trace Tarjan's algorithm by hand on a 6-vertex graph with three SCCs, recording disc/low values at every step.
2. Explain why a cross edge to a vertex not on the stack (already fully processed and popped as part of an earlier SCC) must be ignored in the low-link update — what would go wrong if it weren't?
3. Modify the implementation to also print the condensation graph's edges (which SCCs point to which), by tracking which SCC each vertex belongs to after the algorithm finishes.
4. Challenge: Convert the recursive implementation to a fully iterative one using an explicit call stack, and explain why this matters for very deep graphs (tying back to the recursion-depth discussion in the DFS deep dive).

Limitations