☕ DSA Java Articles

Topics › Graphs › Other Algorithms

Kosaraju's algorithm

Hard TUF ID 498 A2Z

Java source ↗ Edit this article ↗

Problem

You are given a directed graph with n vertices numbered 0 to n - 1 and a list of edges [u, v] meaning u → v. A strongly connected component (SCC) is a maximal set of vertices in which every vertex can reach every other vertex by following edge directions. Find the SCCs; the usual form of the question asks for their number.

The methods in the Java file return the components themselves as lists of vertices; the count is simply the size of that list.

Constraints: 1 ≤ n ≤ 5000, 0 ≤ edges ≤ 5000 in the common version; the algorithm is linear, so much larger graphs are fine.

Example 1

n = 5, edges = [[1,0],[0,2],[2,1],[0,3],[3,4]]
SCCs = {0,1,2}, {3}, {4}       answer = 3
// 0 -> 2 -> 1 -> 0 is a cycle; 3 and 4 can be reached from it but cannot get back

Example 2

n = 8, edges = [[0,1],[1,2],[2,0],[2,3],[3,4],[4,5],[5,6],[6,4],[6,7]]
SCCs = {0,1,2}, {3}, {4,5,6}, {7}   answer = 4

Two facts drive everything below. First, “mutually reachable” is an equivalence relation, so SCCs partition the vertices. Second, if you shrink every SCC to a single node, the resulting condensation graph has no cycles: a cycle between two SCCs would make them mutually reachable, so they would be one SCC. The condensation is a DAG.

Approach 1: Brute force, all-pairs reachability

Intuition. Straight from the definition: u and v are in the same SCC exactly when u reaches v and v reaches u. Run a traversal from every vertex to get a reachability table, then group vertices that reach each other.

Algorithm.

  1. For every vertex s, run DFS and store reach[s][*] (every vertex reaches itself).
  2. Scan vertices in order. For each vertex i not yet assigned, its SCC is every j ≥ i with reach[i][j] && reach[j][i]. Mark them assigned. Vertices before i are already assigned, which is why the inner loop can start at i.
static List<List<Integer>> bruteForce(int n, int[][] edges) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) adj.get(e[0]).add(e[1]);
    boolean[][] reach = new boolean[n][];
    for (int s = 0; s < n; s++) reach[s] = reachableFrom(s, adj);
    boolean[] assigned = new boolean[n];
    List<List<Integer>> sccs = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        if (assigned[i]) continue;
        List<Integer> comp = new ArrayList<>();
        for (int j = i; j < n; j++) {
            if (reach[i][j] && reach[j][i]) {                // mutually reachable
                assigned[j] = true;
                comp.add(j);
            }
        }
        sccs.add(comp);
    }
    return sccs;
}

static boolean[] reachableFrom(int s, List<List<Integer>> adj) {
    boolean[] seen = new boolean[adj.size()];
    Deque<Integer> stack = new ArrayDeque<>();
    seen[s] = true;
    stack.push(s);
    while (!stack.isEmpty()) {
        int u = stack.pop();
        for (int v : adj.get(u)) {
            if (!seen[v]) {
                seen[v] = true;
                stack.push(v);
            }
        }
    }
    return seen;
}

Complexity. Time O(V · (V + E)) for the V traversals, plus O(V^2) for grouping. Space O(V^2) for the reachability table. Fine for a few hundred vertices; Kosaraju does the same job in linear time.

Approach 2: Kosaraju’s algorithm

Intuition. Suppose we could start a DFS inside a sink SCC of the condensation, one with no edges leaving it. That DFS would visit exactly its own SCC and nothing else. Delete it, and some other SCC becomes a sink; repeat. The whole difficulty is finding a vertex in a sink SCC without knowing the SCCs yet. Kosaraju solves it with finish times and a reversed graph.

Finish-time lemma. Run an ordinary DFS over the whole graph and record the moment each vertex finishes (all its descendants are done). If there is an edge from SCC A to a different SCC B, then the latest finish time in A is greater than the latest finish time in B. Why:

Consequence: the vertex that finishes last lies in a source SCC of the condensation, one with no incoming edges from other SCCs.

The reversal trick. Reverse every edge. The SCCs are unchanged (mutual reachability is symmetric), but every edge between SCCs flips direction, so the source SCC we just located becomes a sink in the reversed graph. A DFS from the last-finished vertex on the reversed graph therefore collects exactly one SCC. Then take the next unvisited vertex in decreasing finish order. By the lemma, every reversed edge leaving its SCC points to an SCC with a later finish time, which has already been collected and marked visited. So again the DFS collects exactly one SCC. Repeating until the order is exhausted produces all SCCs.

Algorithm.

  1. Build the adjacency list adj and its transpose rev.
  2. Pass 1: DFS over adj from every unvisited vertex; push each vertex onto a stack finished when it finishes. The top of the stack is the latest finisher.
  3. Reset visited.
  4. Pass 2: pop vertices from the stack. For each unvisited one, run a DFS on rev; everything it visits is one SCC.
static List<List<Integer>> kosaraju(int n, int[][] edges) {
    List<List<Integer>> adj = new ArrayList<>(), rev = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        adj.add(new ArrayList<>());
        rev.add(new ArrayList<>());
    }
    for (int[] e : edges) {
        adj.get(e[0]).add(e[1]);
        rev.get(e[1]).add(e[0]);                              // transpose graph
    }
    boolean[] visited = new boolean[n];
    Deque<Integer> finished = new ArrayDeque<>();
    for (int s = 0; s < n; s++) {                            // pass 1: finish order on the original graph
        if (!visited[s]) dfsOrder(s, adj, visited, finished);
    }
    Arrays.fill(visited, false);
    List<List<Integer>> sccs = new ArrayList<>();
    while (!finished.isEmpty()) {                            // pass 2: latest finisher first, on the transpose
        int s = finished.pop();
        if (visited[s]) continue;
        List<Integer> comp = new ArrayList<>();
        dfsCollect(s, rev, visited, comp);
        sccs.add(comp);
    }
    return sccs;
}

static void dfsOrder(int u, List<List<Integer>> adj, boolean[] visited, Deque<Integer> finished) {
    visited[u] = true;
    for (int v : adj.get(u)) {
        if (!visited[v]) dfsOrder(v, adj, visited, finished);
    }
    finished.push(u);                                        // pushed after all descendants finish
}

static void dfsCollect(int u, List<List<Integer>> rev, boolean[] visited, List<Integer> comp) {
    visited[u] = true;
    comp.add(u);
    for (int v : rev.get(u)) {
        if (!visited[v]) dfsCollect(v, rev, visited, comp);
    }
}

Dry run on example 1. adj: 0: [2, 3], 1: [0], 2: [1], 3: [4]. rev: 0: [1], 1: [2], 2: [0], 3: [0], 4: [3].

Pass 1 from vertex 0: 0 → 2 → 1 (1 sees 0 already visited), so 1 finishes, then 2; next 0 → 3 → 4, so 4 finishes, then 3, then 0. Finish order 1, 2, 4, 3, 0; the stack top is 0.

pop DFS on rev visits SCC
0 0, then 1 (rev[0]), then 2 (rev[1]); rev[2] = 0 already visited {0, 1, 2}
3 3; rev[3] = 0 already visited {3}
4 4; rev[4] = 3 already visited {4}
2, 1 already visited skipped

Three SCCs. Notice how, in pass 2, the reversed edges 3 → 0 and 4 → 3 lead only into components that were already collected; that is the lemma at work.

Complexity. Time O(V + E): two DFS passes plus building the transpose, each linear. Space O(V + E) for the two adjacency lists, plus O(V) for the stack, the visited array and the recursion.

Common misunderstandings

Tarjan’s SCC algorithm finds the same components in one pass using tin and low values, the same tools as bridges and articulation points. Kosaraju is usually easier to remember and to prove.

Edge cases and pitfalls