Tarjan’s SCC Algorithm

Why Tarjan’s SCC Algorithm?

A Strongly Connected Component (SCC) of a directed graph is a maximal set of vertices such that every vertex is reachable from every other vertex in the set. Decomposing a graph into its SCCs is fundamental to problems in dependency analysis, compiler optimisation, and competitive programming.

Tarjan’s algorithm, published in 1972, finds all SCCs in a single depth-first search. Compared to Kosaraju’s two-pass approach, Tarjan’s requires only one DFS traversal and uses an explicit stack to track which vertices might belong to the current SCC.

• Single pass — no need to reverse the graph or run DFS twice
• O(V + E) time and space, same as Kosaraju’s
• Online friendly — SCCs are emitted as soon as they are fully explored
• Foundation for 2-SAT, condensation graphs, and finding bridges/articulation points

The Algorithm

Tarjan’s algorithm maintains two arrays and a stack:

• disc[u] — the discovery time when vertex u is first visited
• low[u] — the smallest discovery time reachable from the subtree rooted at u using at most one back edge
• Stack — holds vertices that may still be part of the current SCC

timer = 0

function dfs(u):
    disc[u] = low[u] = timer++
    stack.push(u);  onStack[u] = true

    for each neighbor v of u:
        if disc[v] == -1:          // tree edge
            dfs(v)
            low[u] = min(low[u], low[v])
        else if onStack[v]:        // back edge
            low[u] = min(low[u], disc[v])

    if disc[u] == low[u]:          // u is SCC root
        pop vertices from stack until u is popped
        → these vertices form one SCC

Key insight: A vertex u is the root of its SCC exactly when disc[u] == low[u]. At that point every vertex above u on the stack belongs to the same SCC. We pop them all off and record the component.

Back-Edge Detection

When we encounter an edge u → v where v is already on the stack, we know there is a path from v back to u (through the DFS tree) and from u to v (the current edge). This cycle means u and v are in the same SCC, so we update low[u] = min(low[u], disc[v]).

Step-by-Step Walkthrough

Trace Tarjan’s algorithm on this 8-node directed graph. The three SCCs are {0, 1, 2}, {3, 4, 5}, and {6, 7}.

Dashed arrows are cross-edges between SCCs. Solid arrows form cycles within each SCC.

Tarjan vs Kosaraju

Both run in O(V + E). Choose Tarjan’s when you want a single pass or need SCCs in reverse topological order. Choose Kosaraju’s when simplicity matters or you already have the transposed graph.

Interactive Animation

Colour key: ● Default   ● On stack   ● Current   ■ SCC found

Condensation Graph (DAG of SCCs)

Once all SCCs are found, contract each SCC into a single super-node. The resulting graph is a DAG (directed acyclic graph) called the condensation. Every edge in the original graph that crosses SCC boundaries becomes an edge in the DAG.

The condensation is useful for:

• Topological ordering of components for dependency resolution
• DP on DAGs — e.g., longest path, counting paths
• Reachability queries — reduce to reachability on the smaller DAG
• 2-SAT — check satisfiability via the implication graph’s SCC structure

C++ Implementation

Tarjan’s SCC

#include <bits/stdc++.h>
using namespace std;

struct TarjanSCC {
    int n, timer = 0;
    vector<vector<int>> adj;
    vector<int> disc, low, stk;
    vector<bool> onStk;
    vector<vector<int>> sccs;

    TarjanSCC(int n) : n(n), adj(n), disc(n, -1),
                       low(n), onStk(n, false) {}

    void addEdge(int u, int v) { adj[u].push_back(v); }

    void dfs(int u) {
        disc[u] = low[u] = timer++;
        stk.push_back(u);
        onStk[u] = true;

        for (int v : adj[u]) {
            if (disc[v] == -1) {
                dfs(v);
                low[u] = min(low[u], low[v]);
            } else if (onStk[v]) {
                low[u] = min(low[u], disc[v]);
            }
        }

        if (disc[u] == low[u]) {
            vector<int> scc;
            while (true) {
                int v = stk.back(); stk.pop_back();
                onStk[v] = false;
                scc.push_back(v);
                if (v == u) break;
            }
            sccs.push_back(scc);
        }
    }

    void findSCCs() {
        for (int i = 0; i < n; i++)
            if (disc[i] == -1) dfs(i);
    }
};

Condensation Graph Builder

// Returns {condensation DAG adjacency, comp[v] = SCC index of v}
pair<vector<vector<int>>, vector<int>>
buildCondensation(TarjanSCC& t) {
    int k = t.sccs.size();
    vector<int> comp(t.n);
    for (int i = 0; i < k; i++)
        for (int v : t.sccs[i])
            comp[v] = i;

    vector<vector<int>> dag(k);
    set<pair<int,int>> seen;
    for (int u = 0; u < t.n; u++)
        for (int v : t.adj[u])
            if (comp[u] != comp[v])
                if (seen.insert({comp[u], comp[v]}).second)
                    dag[comp[u]].push_back(comp[v]);

    return {dag, comp};
}

Usage Example

int main() {
    int n, m; cin >> n >> m;
    TarjanSCC g(n);
    while (m--) {
        int u, v; cin >> u >> v;
        g.addEdge(u, v);
    }
    g.findSCCs();

    // Print SCCs
    for (auto& scc : g.sccs) {
        for (int v : scc) cout << v << ' ';
        cout << '\n';
    }

    // Build and use condensation
    auto [dag, comp] = buildCondensation(g);
    // dag is a DAG — apply topological sort, DP, etc.
}

Complexity Analysis

Every vertex is pushed and popped from the stack exactly once, and each edge is examined once during the DFS. The low-link updates are O(1) per edge. This makes Tarjan’s algorithm optimal for SCC decomposition.

Practical note: The recursive DFS can overflow the call stack for very large graphs (V > 10⁶). In competitive programming, either increase the stack size or convert to an iterative implementation.

Practice Problems

1. CSES. Planets and Kingdoms — Direct SCC decomposition
2. CSES. Coin Collector — SCC condensation + DP on DAG
3. Codeforces 427C. Checkposts — Min-cost vertex per SCC
4. LeetCode 1192. Critical Connections in a Network — Tarjan’s bridges variant
5. LeetCode 2360. Longest Cycle in a Graph — Cycle detection via SCC ideas
6. Codeforces 22E. Scheme — Make a graph strongly connected

Summary

• Tarjan’s algorithm finds all SCCs in O(V + E) with a single DFS pass.
• It uses disc[] and low[] arrays plus an explicit stack to detect SCC roots.
• A vertex u is an SCC root when disc[u] == low[u]; pop the stack down to u to extract the component.
• The condensation graph collapses each SCC into a node, yielding a DAG for further algorithms (DP, topological sort).
• Compared to Kosaraju, Tarjan needs only one DFS and no transposed graph.
• The same low-link idea powers algorithms for bridges and articulation points.