Strongly Connected Components (Kosaraju's)

Description

In a directed graph, two nodes are strongly connected when each can reach the other. The maximal groups of mutually reachable nodes are the strongly connected components (SCCs). They're the parts of the graph where following edges can bring you back. Kosaraju's algorithm finds them all in O(V + E) with two traversals. Collapsing each SCC into a single node turns any directed graph into a DAG, which makes many hard-looking questions simple.

We'll go from simple to more technical:

1. The pattern: Kosaraju's algorithm, two DFS passes with a transpose between them.
2. A second flavor: the condensation DAG, and the minimum number of starting points.
3. Where SCCs show up (dependency knots, link structure, reachability).
4. What breaks it: the order of pass 2, skipping the transpose, and counting nodes instead of components.

The approach

List<List<Integer>> stronglyConnectedComponents(int n, List<List<Integer>> adj) {
    boolean[] visited = new boolean[n];
    Deque<Integer> finished = new ArrayDeque<>();
    for (int v = 0; v < n; v++) if (!visited[v]) fillOrder(v, adj, visited, finished);   // pass 1

    List<List<Integer>> transpose = new ArrayList<>();
    for (int v = 0; v < n; v++) transpose.add(new ArrayList<>());
    for (int u = 0; u < n; u++) for (int v : adj.get(u)) transpose.get(v).add(u);      // reverse every edge

    Arrays.fill(visited, false);
    List<List<Integer>> sccs = new ArrayList<>();
    while (!finished.isEmpty()) {
        int v = finished.pop();                          // latest finisher first
        if (!visited[v]) {
            List<Integer> component = new ArrayList<>();
            collect(v, transpose, visited, component);   // pass 2: one fresh DFS = one SCC
            sccs.add(component);
        }
    }
    return sccs;
}

void fillOrder(int v, List<List<Integer>> adj, boolean[] visited, Deque<Integer> finished) {
    visited[v] = true;
    for (int next : adj.get(v)) if (!visited[next]) fillOrder(next, adj, visited, finished);
    finished.push(v);                                    // pushed only after everything reachable is done
}

def strongly_connected_components(n: int, adj: list[list[int]]) -> list[list[int]]:
    visited = [False] * n
    finished = []                                        # a list as a stack: append / pop
    for v in range(n):
        if not visited[v]:
            fill_order(v, adj, visited, finished)        # pass 1

    transpose = [[] for _ in range(n)]
    for u in range(n):
        for v in adj[u]:
            transpose[v].append(u)                       # reverse every edge

    visited = [False] * n
    sccs = []
    while finished:
        v = finished.pop()                               # latest finisher first
        if not visited[v]:
            component = []
            collect(v, transpose, visited, component)    # pass 2: one fresh DFS = one SCC
            sccs.append(component)
    return sccs


def fill_order(v: int, adj: list[list[int]], visited: list[bool], finished: list[int]) -> None:
    visited[v] = True
    for nxt in adj[v]:
        if not visited[nxt]:
            fill_order(nxt, adj, visited, finished)
    finished.append(v)                                   # pushed only after everything reachable is done

The node that finishes last in pass 1 lies in a "source" component - one that nothing outside it can reach. In the transposed graph that component becomes a sink: a DFS from it can't leave. So pass 2, taking nodes in reverse finish order, always starts inside a component whose exits (in the transposed graph) lead only to components already collected. Each fresh DFS therefore picks up exactly one SCC.

A second flavor: the condensation

Collapse each SCC into a single node and keep the edges between different components: the result is always a DAG, because two components that could reach each other would have been one component. Questions about graphs with cycles often become simple DAG questions there. How many starting points are needed so that every node is reachable from at least one? One per component that no edge enters:

boolean[] entered = new boolean[componentCount];
for (int u = 0; u < n; u++)
    for (int v : adj.get(u))
        if (comp[u] != comp[v]) entered[comp[v]] = true;   // an edge from another component
int starts = 0;
for (boolean e : entered) if (!e) starts++;

entered = [False] * component_count
for u in range(n):
    for v in adj[u]:
        if comp[u] != comp[v]:
            entered[comp[v]] = True                      # an edge from another component
starts = entered.count(False)

Counting nodes with in-degree zero gets this wrong as soon as there's a cycle: a 3-cycle has no node with in-degree zero, yet it needs one starting point.

Where you'll see it

SCCs find circular dependencies (the packages that must be built or loaded together), mutually recursive functions in a call graph, and tightly linked clusters of web pages or accounts. Compilers use the condensation to process groups of mutually dependent definitions in a valid order; 2-SAT solvers decide satisfiability by checking whether a variable and its negation share an SCC.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. With edges 0->2, 2->1, 1->0, 0->3 and 3->4, what are the SCCs?

2. Why must pass 2 run on the transposed graph?

3. A graph is a single 3-cycle. How many starting points are needed to reach every node, and why does counting in-degree-zero nodes fail?

Key takeaways

• An SCC is a maximal set of nodes that can all reach each other.
• Kosaraju: DFS to record finish order, then DFS on the transposed graph in reverse finish order - each fresh DFS is one SCC.
• Both the order and the transpose are required; either mistake merges components.
• Collapsing SCCs gives a DAG (the condensation), where cyclic-graph questions become DAG questions.
• O(V + E) time and space; Tarjan's algorithm does it in one pass.