Count Strongly connected Components (Kosaraju Algo)

The problem, simply

You get a directed graph: V dots and one-way arrows between them. A strongly connected group is a largest possible set of dots where every dot can reach every other dot in the set by following arrows.

Every dot belongs to exactly one such group, even if the group is only that one dot. Count the groups.

A story to remember it

Picture it

Examples

Way 1: the simple way

Two dots are in the same group exactly when each can reach the other. So find out who can reach whom.

1. From every dot, run a search and mark all dots it can reach. This fills a V by V table reach.
2. Go through the dots. If a dot has no group yet, start a new group and add every dot j with reach[i][j] and reach[j][i].
3. The number of groups started is the answer.

class SccBrute {
    public static int countGroups(int V, List<List<Integer>> adj) {
        boolean[][] reach = new boolean[V][V];
        for (int s = 0; s < V; s++) {                 // one search from every dot
            Deque<Integer> line = new ArrayDeque<>();
            line.add(s);
            reach[s][s] = true;
            while (!line.isEmpty()) {
                int u = line.poll();
                for (int v : adj.get(u)) {
                    if (!reach[s][v]) { reach[s][v] = true; line.add(v); }
                }
            }
        }
        boolean[] placed = new boolean[V];
        int groups = 0;
        for (int i = 0; i < V; i++) {
            if (placed[i]) continue;
            groups++;
            for (int j = i; j < V; j++) {
                if (reach[i][j] && reach[j][i]) placed[j] = true;   // they reach each other
            }
        }
        return groups;
    }
}

How long it takes: V searches of O(V + E) each, O(V * (V + E)). Extra room: the reach table, O(V^2).

Way 2: the clever way

Kosaraju's idea uses two depth first walks.

1. Pass 1: walk the real arrows. When a dot has no new dot left to visit, it is finished; push it on a pile. Do this from every unvisited dot.
2. Flip every arrow.
3. Pass 2: pop dots off the pile. If the dot has no group yet, walk the flipped arrows from it, and put every new dot you reach into one new group.

Why it works: the dot that finished last sits in a "source" club, one that no other unvisited club points into. With arrows flipped, a walk from it cannot leak out of its own club. Each later pop starts in the next club the same way.

class Kosaraju {
    public static int countGroups(int V, List<List<Integer>> adj) {
        boolean[] seen = new boolean[V];
        Deque<Integer> finished = new ArrayDeque<>();     // the finished pile
        for (int i = 0; i < V; i++) {
            if (!seen[i]) walk(i, adj, seen, finished);
        }

        List<List<Integer>> flipped = new ArrayList<>();
        for (int i = 0; i < V; i++) flipped.add(new ArrayList<>());
        for (int u = 0; u < V; u++) {
            for (int v : adj.get(u)) flipped.get(v).add(u);   // u to v becomes v to u
        }

        Arrays.fill(seen, false);
        int groups = 0;
        while (!finished.isEmpty()) {
            int u = finished.pop();                       // last finished comes first
            if (seen[u]) continue;
            walkFlipped(u, flipped, seen);                // everything reached is one group
            groups++;
        }
        return groups;
    }

    static void walk(int u, List<List<Integer>> adj, boolean[] seen, Deque<Integer> finished) {
        seen[u] = true;
        for (int v : adj.get(u)) {
            if (!seen[v]) walk(v, adj, seen, finished);
        }
        finished.push(u);                                 // nothing new left from u
    }

    static void walkFlipped(int u, List<List<Integer>> flipped, boolean[] seen) {
        seen[u] = true;
        for (int v : flipped.get(u)) {
            if (!seen[v]) walkFlipped(v, flipped, seen);
        }
    }

    public static void main(String[] args) {
        int V = 7;
        int[][] edges = {{0, 1}, {1, 2}, {2, 0}, {1, 3}, {3, 4}, {4, 5}, {5, 3}, {5, 6}};
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) adj.get(e[0]).add(e[1]);
        System.out.println(countGroups(V, adj));         // 3
    }
}

How long it takes: two walks over every dot and arrow, plus building the flipped arrows, O(V + E). Extra room: the flipped graph O(V + E), and the pile and the call stack O(V).

Watch out for

• Walking the original arrows in pass 2 is wrong. You must flip them.
• Push a dot after all its children are done, not when you first visit it. Visit order is not finish order.
• Run pass 1 from every unvisited dot, not only from dot 0, or dots unreachable from 0 never get on the pile.
• Recursion can be V calls deep. For a million dots, rewrite the walks with your own stack.

What interviewers ask next

• Tarjan's way: one pass with discovery times and a "lowest reachable time" per dot. A dot whose lowest time equals its own time starts a club, and you pop that club off a stack. Same O(V + E), no flipping.
• Squash each club into a single dot. The result has no loops at all, which helps solve problems like 2-SAT or "minimum roads to make everything reachable".
• 2-SAT: each true or false variable becomes two dots. The formula is solvable exactly when no variable and its opposite land in the same club.
• Why does flipping keep the clubs the same? If A reaches B and B reaches A, flipped arrows still let them reach each other. Only the one-way links between clubs change direction.

Remember this

Grown-up words: kids are vertices, one-way note routes are directed edges, a club is a strongly connected component, the finished pile is the finish order stack, flipping the arrows builds the transpose graph, and this two-pass method is Kosaraju's algorithm.