Tarjan's SCC Algorithm

A Bit of History

In 1972, Robert Tarjan published Depth-First Search and Linear Graph Algorithms, showing how information gathered during DFS could solve several structural graph problems in linear time. The paper's influence is easy to underestimate: its low-link idea underlies classic algorithms for strongly connected components, articulation points, and bridges.

The SCC version is especially elegant. Kosaraju's algorithm separates the work into two DFS passes and reverses every edge between them. Tarjan instead keeps the unresolved part of the first DFS in memory and recognizes the exact moment an entire component becomes complete. Both are linear-time algorithms; Tarjan's distinctive advantage is a single traversal without explicitly constructing the transpose graph.

What Are We Actually Finding?

In a directed graph, a strongly connected component (SCC) is a maximal set of vertices in which every vertex can reach every other vertex. “Maximal” matters: a directed cycle is strongly connected, but if another vertex can travel into the cycle and back out to itself, that vertex belongs to the same SCC too.

SCCs partition the graph. Every vertex belongs to exactly one component, including an isolated vertex or a vertex with no return path; such a vertex forms a singleton SCC. Once each SCC is contracted into one super-vertex, the result is always a directed acyclic graph called the condensation graph. If the condensation contained a directed cycle, all super-vertices on that cycle would be mutually reachable and should have been one SCC.

The Three Pieces of State

Tarjan's algorithm assigns two integers and one membership flag to each vertex. The names vary across implementations—disc, index, or id—but their jobs should remain distinct.

The Algorithm, Step by Step

1. Discover a vertex. Set index[v] = low[v] to the next timestamp, push v onto the active stack, and mark it active.
2. Inspect each outgoing edge v → w. The update depends on whether w is unvisited, active, or already assigned to a component.
3. Finish the vertex. After every outgoing edge has been processed, test whether low[v] == index[v].
4. Emit a component. If equality holds, repeatedly pop the active stack until v is popped. Those popped vertices form exactly one SCC.
5. Cover disconnected regions. Start DFS from every still-unvisited vertex, not only from an arbitrary first vertex.

The root test is the algorithm's hinge:

$$\operatorname{low}[v] = \operatorname{index}[v] \quad\Longrightarrow\quad v\text{ begins a complete SCC on the active stack.}$$

The Three Edge Rules

Most implementation bugs come from collapsing the following cases into one generic “visited neighbor” rule. Keep them separate.

Visual Walkthrough

Consider two cycles connected by a one-way edge: $A \to B \to C \to A$, $D \leftrightarrow E$, and $C \to D$. DFS follows the vertices in alphabetical neighbor order. The labels below are index / low after the relevant back edges have propagated.

Why the Root Test Works

A useful proof can be organized around three invariants rather than one leap of intuition.

1. The active stack contains exactly the unresolved vertices

A vertex is pushed when discovered and popped only when assigned to an SCC. Consequently, an edge to an inactive vertex enters a component that has already been finalized. Letting that edge lower a current low-link would incorrectly combine a one-way dependency with mutual reachability.

2. Low-link values summarize active return routes

After processing v's outgoing edges, low[v] is the earliest active discovery index reachable from the DFS region rooted at v, as captured by the recurrence. A tree child contributes its entire unresolved reachability summary, low[child]. A direct edge to an active vertex contributes that target's fixed index.

3. Equality marks the oldest vertex in one unresolved SCC

If low[v] < index[v], the unresolved region beneath v can reconnect to an older active vertex, so closing a component at v would be premature. If low[v] == index[v], no vertex in that unresolved region can reach an active vertex older than v. The vertices above v that belong to its DFS region are reachable from v; the propagated low-link relationships that kept them unresolved provide return routes within the same active region. Popping through v therefore extracts a mutually reachable set. It is maximal because any older active vertex is unreachable from that set, and any already-popped vertex belongs to a previously sealed SCC.

Every vertex is eventually popped exactly once, so these maximal sets are disjoint and cover the entire graph.

Complexity Analysis

Every vertex is discovered once, pushed once, and popped once. Every directed edge is inspected once in an adjacency-list representation.

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

The adjacency list itself occupies $O(V+E)$ space. A recursive implementation can also consume $O(V)$ call-stack frames in the worst case, such as one long directed path. For very deep or adversarial graphs, use an iterative implementation or a language/runtime with a safely configured stack.

Implementation

These versions keep all mutable state local to one run, cover disconnected graphs, and use the exact three-way edge logic described above. The Python version also returns component IDs and condensation edges; the C++ and Java versions expose component IDs so the same final edge scan can be added directly.

def tarjan_scc(vertices, edges):
    """Return (components, component_of, condensation_edges).

    Vertices appearing only in edges are included automatically.
    Components are emitted in reverse topological order.
    """
    ordered = list(dict.fromkeys(vertices))
    known = set(ordered)
    edge_list = list(edges)
    for u, v in edge_list:
        if u not in known:
            ordered.append(u)
            known.add(u)
        if v not in known:
            ordered.append(v)
            known.add(v)

    adjacency = {v: [] for v in ordered}
    for u, v in edge_list:
        adjacency[u].append(v)

    next_index = 0
    index = {}
    low = {}
    stack = []
    on_stack = set()
    components = []
    component_of = {}

    def strong_connect(v):
        nonlocal next_index
        index[v] = low[v] = next_index
        next_index += 1
        stack.append(v)
        on_stack.add(v)

        for w in adjacency[v]:
            if w not in index:                  # DFS-tree edge
                strong_connect(w)
                low[v] = min(low[v], low[w])
            elif w in on_stack:                 # edge to active vertex
                low[v] = min(low[v], index[w])  # index[w], not low[w]
            # Edge to a popped vertex: deliberately ignored.

        if low[v] == index[v]:
            component_id = len(components)
            component = []
            while True:
                w = stack.pop()
                on_stack.remove(w)
                component_of[w] = component_id
                component.append(w)
                if w == v:
                    break
            components.append(component)

    for v in ordered:                            # handles disconnected graphs
        if v not in index:
            strong_connect(v)

    condensation_edges = {
        (component_of[u], component_of[v])
        for u, v in edge_list
        if component_of[u] != component_of[v]
    }
    return components, component_of, condensation_edges


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

components, component_of, dag_edges = tarjan_scc(vertices, edges)
print(components)    # [['F'], ['E', 'D'], ['C', 'B', 'A']]
print(dag_edges)     # {(2, 1), (1, 0)}; set display order may vary

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>

class TarjanSCC {
public:
    explicit TarjanSCC(std::vector<std::vector<int>> graph)
        : adj_(std::move(graph)), nextIndex_(0),
          index_(adj_.size(), -1), low_(adj_.size()),
          componentOf_(adj_.size(), -1), onStack_(adj_.size(), false) {}

    std::vector<std::vector<int>> run() {
        for (int v = 0; v < static_cast<int>(adj_.size()); ++v) {
            if (index_[v] == -1) strongConnect(v);
        }
        return components_;
    }

    const std::vector<int>& componentOf() const { return componentOf_; }

private:
    void strongConnect(int v) {
        index_[v] = low_[v] = nextIndex_++;
        stack_.push_back(v);
        onStack_[v] = true;

        for (int w : adj_[v]) {
            if (index_[w] == -1) {
                strongConnect(w);
                low_[v] = std::min(low_[v], low_[w]);
            } else if (onStack_[w]) {
                low_[v] = std::min(low_[v], index_[w]);
            }
        }

        if (low_[v] == index_[v]) {
            int id = static_cast<int>(components_.size());
            std::vector<int> component;
            while (true) {
                int w = stack_.back();
                stack_.pop_back();
                onStack_[w] = false;
                componentOf_[w] = id;
                component.push_back(w);
                if (w == v) break;
            }
            components_.push_back(std::move(component));
        }
    }

    std::vector<std::vector<int>> adj_;
    int nextIndex_;
    std::vector<int> index_, low_, stack_, componentOf_;
    std::vector<bool> onStack_;
    std::vector<std::vector<int>> components_;
};

int main() {
    std::vector<std::vector<int>> graph = {
        {1},       // A -> B
        {2},       // B -> C
        {0, 3},    // C -> A, D
        {4},       // D -> E
        {3, 5},    // E -> D, F
        {}         // F
    };

    TarjanSCC solver(graph);
    auto components = solver.run();
    std::cout << "Number of SCCs: " << components.size() << '\n'; // 3
}

import java.util.*;

public class TarjanSCC {
    static final class Solver {
        private final List<List<Integer>> graph;
        private final int[] index, low, componentOf;
        private final boolean[] onStack;
        private final Deque<Integer> stack = new ArrayDeque<>();
        private final List<List<Integer>> components = new ArrayList<>();
        private int nextIndex = 0;

        Solver(List<List<Integer>> graph) {
            this.graph = graph;
            int n = graph.size();
            index = new int[n];
            low = new int[n];
            componentOf = new int[n];
            onStack = new boolean[n];
            Arrays.fill(index, -1);
            Arrays.fill(componentOf, -1);
        }

        List<List<Integer>> run() {
            for (int v = 0; v < graph.size(); v++) {
                if (index[v] == -1) strongConnect(v);
            }
            return components;
        }

        int[] componentIds() { return componentOf.clone(); }

        private void strongConnect(int v) {
            index[v] = low[v] = nextIndex++;
            stack.push(v);
            onStack[v] = true;

            for (int w : graph.get(v)) {
                if (index[w] == -1) {
                    strongConnect(w);
                    low[v] = Math.min(low[v], low[w]);
                } else if (onStack[w]) {
                    low[v] = Math.min(low[v], index[w]);
                }
            }

            if (low[v] == index[v]) {
                int id = components.size();
                List<Integer> component = new ArrayList<>();
                while (true) {
                    int w = stack.pop();
                    onStack[w] = false;
                    componentOf[w] = id;
                    component.add(w);
                    if (w == v) break;
                }
                components.add(component);
            }
        }
    }

    public static void main(String[] args) {
        List<List<Integer>> graph = List.of(
            List.of(1), List.of(2), List.of(0, 3),
            List.of(4), List.of(3, 5), List.of()
        );
        Solver solver = new Solver(graph);
        System.out.println(solver.run()); // [[5], [4, 3], [2, 1, 0]]
    }
}

From Components to a Condensation DAG

Finding SCCs is often only the preprocessing step. Assign each vertex a component ID while popping it, then scan the original edges once more. For every edge $u \to v$ with different component IDs, add the edge $\operatorname{comp}(u) \to \operatorname{comp}(v)$. Deduplicate repeated component edges with a set.

The Python implementation above returns this mapping and edge set directly. Because the result is a DAG, problems that were awkward on the cyclic original graph often become straightforward:

• topologically order dependency groups;
• run shortest-path, longest-path, or counting DP over components;
• identify source components with no incoming dependencies and sink components with no outgoing dependencies;
• reason about reachability at component scale instead of vertex scale.

Tarjan vs. Kosaraju

Neither algorithm is asymptotically faster. Choose Kosaraju when two simple passes and a reverse graph fit naturally. Choose Tarjan when one pass, no transpose, or immediate component emission fits the surrounding system better. For memory-constrained or enormous graphs, representation details, recursion depth, and data locality may matter more than the headline complexity.

Where SCCs Earn Their Keep

Pitfalls and Defensive Checks

Exercises