Strongly Connected Components

"Tarjan's and Kosaraju's algorithms. Condense cycles into DAG of SCCs."

A strongly connected component (SCC) is a maximal set of vertices such that every vertex is reachable from every other. SCCs let you condense a directed graph into a DAG (condensation). Algorithms: Tarjan's (single DFS, stack, low-link values) and Kosaraju's (two DFS passes on original and reversed graph). Applications: 2-SAT, finding cycles, simplifying graph structure.

15 min readgraph problems →

Problems you can solve with this pattern

4 problems · click any to start solving

All graph →

1Course Schedule IIMediumSolve

2Number of ProvincesMediumSolve

3Critical Connections in a NetworkHardSolve

4Redundant Connection IIHardSolve

Tarjan's SCC algorithm

function tarjanSCC(graph, n) {
    const disc = new Array(n).fill(-1);
    const low = new Array(n).fill(0);
    const onStack = new Array(n).fill(false);
    const stack = [];
    const sccs = [];
    let timer = 0;

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

        for (const v of (graph[u] || [])) {
            if (disc[v] === -1) {
                dfs(v);
                low[u] = Math.min(low[u], low[v]);
            } else if (onStack[v]) {
                low[u] = Math.min(low[u], disc[v]);
            }
        }

        // u is root of an SCC
        if (low[u] === disc[u]) {
            const scc = [];
            let w;
            do {
                w = stack.pop();
                onStack[w] = false;
                scc.push(w);
            } while (w !== u);
            sccs.push(scc);
        }
    }

    for (let i = 0; i < n; i++) if (disc[i] === -1) dfs(i);
    return sccs; // SCCs in reverse topological order
}

Tarjan's SCC: DFS with discovery time and low-link values. low[v] = min discovery time reachable from subtree of v (via back/cross edges). If low[v] == disc[v], v is root of an SCC — pop stack until v. Kosaraju's: (1) DFS on original graph, push to stack in finish order. (2) Transpose graph. (3) DFS on transposed graph in reverse finish order — each DFS tree is one SCC. Both O(V+E).

Tarjan's SCC algorithm

function tarjanSCC(graph, n) {
    const disc = new Array(n).fill(-1);
    const low = new Array(n).fill(0);
    const onStack = new Array(n).fill(false);
    const stack = [];
    const sccs = [];
    let timer = 0;

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

        for (const v of (graph[u] || [])) {
            if (disc[v] === -1) {
                dfs(v);
                low[u] = Math.min(low[u], low[v]);
            } else if (onStack[v]) {
                low[u] = Math.min(low[u], disc[v]);
            }
        }

        // u is root of an SCC
        if (low[u] === disc[u]) {
            const scc = [];
            let w;
            do {
                w = stack.pop();
                onStack[w] = false;
                scc.push(w);
            } while (w !== u);
            sccs.push(scc);
        }
    }

    for (let i = 0; i < n; i++) if (disc[i] === -1) dfs(i);
    return sccs; // SCCs in reverse topological order
}

Medium

Medium

Critical Connections in a Network

Hard

Solve

Redundant Connection II

Hard

Solve

Tarjan's SCC key insight: low[v] = min discovery time reachable via any path (back edges). If low[v] == disc[v], v is the root of an SCC — everything on the stack above v forms the SCC.

Condensation DAG: After finding SCCs, contract each SCC to a single node. The result is a DAG — useful for 2-SAT, shortest path in graphs with cycles.

Bridges vs SCCs: Bridge = edge not in any SCC of size ≥ 2. Articulation point = vertex whose removal increases component count. Both use the same low-link technique.

← Top-K & Streaming Algorithms Binary Lifting →