Lesson 37.2 · Advanced Graph Algorithms

Strongly Connected Components

In a directed graph, an SCC is a maximal set where every node reaches every other. Kosaraju finds them with two DFS passes; Tarjan with one pass and low-links.

14 min

Think of it like this

One-way streets in a town: a neighbourhood where you can drive from any house to any other and back is one component. Leaving it might be possible, but you can't return.

1.Kosaraju in two passes

1. DFS the original graph, recording nodes in finishing order. 2. Reverse every edge. 3. Take nodes in reverse finishing order; each DFS on the reversed graph from an unvisited node collects exactly one SCC.

Collapsing each SCC to one node gives a DAG (the condensation), so topological sort and DP on DAGs apply to any directed graph after this step. That is how 2-SAT, dependency cycles and "minimum sources to reach all" are solved.

Main.java

import java.util.*;

public class Main {
    static List<List<Integer>> g = new ArrayList<>(), rg = new ArrayList<>();
    static boolean[] seen;
    static Deque<Integer> order = new ArrayDeque<>();

    static void dfs1(int u) { seen[u] = true; for (int v : g.get(u)) if (!seen[v]) dfs1(v); order.push(u); }
    static void dfs2(int u, List<Integer> comp) { seen[u] = true; comp.add(u); for (int v : rg.get(u)) if (!seen[v]) dfs2(v, comp); }

    public static void main(String[] args) {
        int n = 5;
        int[][] edges = {{0, 1}, {1, 2}, {2, 0}, {1, 3}, {3, 4}};
        for (int i = 0; i < n; i++) { g.add(new ArrayList<>()); rg.add(new ArrayList<>()); }
        for (int[] e : edges) { g.get(e[0]).add(e[1]); rg.get(e[1]).add(e[0]); }
        seen = new boolean[n];
        for (int i = 0; i < n; i++) if (!seen[i]) dfs1(i);
        seen = new boolean[n];
        while (!order.isEmpty()) {                  // reverse finishing order
            int u = order.pop();
            if (seen[u]) continue;
            List<Integer> comp = new ArrayList<>();
            dfs2(u, comp);
            System.out.println(comp);
        }
    }
}

Output

[0, 2, 1]
[3]
[4]

Remember

SCC = mutually reachable.
Kosaraju: finish order, reverse, DFS again.
Condensation is a DAG.

Common mistakes

Running the second pass on the original graph.

Command Palette

Strongly Connected Components

1.Kosaraju in two passes