Problem 37.3 · Advanced Graph AlgorithmsMedium

Count Strongly Connected Components

PatternGraph DFS and Flood Fill Topological Sort

What it teaches: Kosaraju's two passes.

In plain words

In a one-way road map, a strongly connected group is a set of towns where you can drive from any of them to any other. Kosaraju's trick: do a DFS and note when each town is finished. Then flip every road and explore towns in reverse finishing order; each new exploration traps exactly one group.

Return the number of groups. Example: n = 5, [[0,1],[1,2],[2,0],[1,3],[3,4]] → 3.

The problem

Given a directed graph with n nodes and an edge list, return the number of strongly connected components.

Example 1

Input: n = 5, edges = [[0,1],[1,2],[2,0],[1,3],[3,4]]
Output: 3

Constraints

1 ≤ n ≤ 10⁴

Pattern clues in the wording

→ Directed graph
→ Mutually reachable groups

These clues point to Graph DFS and Flood Fill: Go as deep as possible from a node, marking visited cells or nodes, to find connected regions.

Stuck? Take one hint at a time

Solution · starter

import java.util.*;

class Solution {
    public int countSCC(int n, int[][] edges) {
        return 0;
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#	Input	Expected
1	n = 5 edges = [[0,1],[1,2],[2,0],[1,3],[3,4]]	3
2	n = 3 edges = [[0,1],[1,2]]	3
3	n = 4 edges = [[0,1],[1,0],[2,3],[3,2]]	2

From slow to fast

Approaches

1. Kosaraju · O(V + E)

Kosaraju

Time O(V + E) Space O(V + E)

Iterative finish-order DFS, then count DFS starts on the reversed graph.

▶ Dry run: Kosaraju: finish order, then reversed edgesn = 5, edges = [[0,1],[1,2],[2,0],[1,3],[3,4]]

finish order(list)

24310

Step 1/4First DFS from 0: 2 finishes first, then 4, 3, 1 and finally 0. Each is pushed on a stack, so 0 is on top.

Approach 1

import java.util.*;

class Solution {
    private List<List<Integer>> g, rg;
    private boolean[] seen;
    private final Deque<Integer> order = new ArrayDeque<>();

    public int countSCC(int n, int[][] edges) {
        g = new ArrayList<>();
        rg = new ArrayList<>();
        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]) finish(i);
        seen = new boolean[n];
        int count = 0;
        while (!order.isEmpty()) {
            int u = order.pop();
            if (seen[u]) continue;
            count++;
            collect(u);
        }
        return count;
    }

    private void finish(int u) {
        seen[u] = true;
        for (int v : g.get(u)) if (!seen[v]) finish(v);
        order.push(u);
    }

    private void collect(int u) {
        seen[u] = true;
        for (int v : rg.get(u)) if (!seen[v]) collect(v);
    }
}

Verdict: Two simple passes.

Before you submit

Edge cases and common mistakes

Test these inputs

No edges (n components)
One big cycle (1)

Mistakes people make

Counting weakly connected components (ignoring direction).

Interview

Follow-up questions

How does Tarjan's algorithm do it in one pass?

Command Palette

The problem

Approaches

Kosaraju

Edge cases and common mistakes

Follow-up questions