☕ DSA Java Articles

Topics › Graphs › Other Algorithms

Strongly Connected Component(using KosaRaju's algo)

Hard TUF ID 2811 SDE

Java source ↗ Edit this article ↗

Problem

You are given a directed graph with V vertices numbered 0 to V - 1 and a list of edges {u, v}, each meaning “there is an edge from u to v”. Two vertices belong to the same strongly connected component (SCC) when each one can reach the other by following edge directions. Every vertex belongs to exactly one SCC; a vertex that nothing leads back to forms a component on its own.

Return all the strongly connected components. The usual version (GFG, “Strongly Connected Components (Kosaraju’s Algo)”) asks only for the number of components, which is the size of the returned list. Each component is sorted, and components are ordered by their smallest vertex.

Constraints in the usual version: 1 ≤ V ≤ 5000, 0 ≤ E ≤ V(V - 1). Self loops and repeated edges may appear.

Example 1

V = 5, edges = [1→0, 0→2, 2→1, 0→3, 3→4]
answer = [[0, 1, 2], [3], [4]]      // 0→2→1→0 is a cycle; nothing returns from 3 or 4

Example 2

V = 8, edges = [0→1, 1→2, 2→0, 2→3, 3→4, 4→5, 5→6, 6→4, 6→7]
answer = [[0, 1, 2], [3], [4, 5, 6], [7]]   // two cycles joined by the one-way path 2→3→4

All approaches share two helpers: one builds the adjacency list, the other puts the answer in the canonical order described above.

static List<List<Integer>> buildAdj(int V, int[][] edges) {
    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]);
    return adj;
}

/** Sorts each component, then orders components by their smallest vertex, so answers can be compared directly. */
static List<List<Integer>> normalise(List<List<Integer>> comps) {
    for (List<Integer> c : comps) Collections.sort(c);
    comps.sort((a, b) -> Integer.compare(a.get(0), b.get(0)));
    return comps;
}

Approach 1: Brute force, pairwise reachability

Intuition. The definition says u and v share a component exactly when u reaches v and v reaches u. So compute, for every start vertex s, the full set of vertices reachable from s with one graph traversal, and store the results in a V × V boolean matrix. Mutual reachability is an equivalence relation (if u ↔ v and v ↔ w, then u → v → w and w → v → u), so grouping each unassigned vertex with everything mutually reachable from it produces disjoint classes, and those classes are the SCCs.

Algorithm.

  1. For each vertex s, run an iterative DFS and mark reach[s][v] for every vertex v it visits (including s itself).
  2. Scan vertices in increasing order. For an unassigned u, collect every unassigned v ≥ u with reach[u][v] && reach[v][u] into a new component.
  3. Normalise and return the components.

Starting the inner scan at v = u is enough: if some smaller v belonged with u, then u would already have been assigned when v was processed.

static List<List<Integer>> bruteForce(int V, int[][] edges) {
    List<List<Integer>> adj = buildAdj(V, edges);
    boolean[][] reach = new boolean[V][V];                 // reach[s][v]: there is a path s -> v
    for (int s = 0; s < V; s++) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(s);
        reach[s][s] = true;
        while (!stack.isEmpty()) {
            int u = stack.pop();
            for (int v : adj.get(u)) {
                if (!reach[s][v]) {
                    reach[s][v] = true;
                    stack.push(v);
                }
            }
        }
    }
    boolean[] assigned = new boolean[V];
    List<List<Integer>> comps = new ArrayList<>();
    for (int u = 0; u < V; u++) {
        if (assigned[u]) continue;
        List<Integer> comp = new ArrayList<>();
        for (int v = u; v < V; v++) {
            if (!assigned[v] && reach[u][v] && reach[v][u]) {
                assigned[v] = true;
                comp.add(v);
            }
        }
        comps.add(comp);
    }
    return normalise(comps);
}

Complexity. Time O(V · (V + E)): one full traversal per vertex, plus O(V^2) for the grouping scan. Space O(V^2) for the reachability matrix. With V = 5000 and a dense graph this is around 10^11 steps, because every traversal rediscovers what earlier ones already explored.

Approach 2: Optimal, Kosaraju’s algorithm

Intuition. Shrink every SCC to a single node. The resulting condensation graph is a DAG: if two components could reach each other, they would be one component. In that DAG, look at a sink component, one with no edges leaving it. A DFS started anywhere inside a sink component visits exactly that component, because there is no way out. So if we could always start from a vertex in a sink, mark what we reach, and repeat, we would peel off the SCCs one at a time. The problem is finding a sink.

Kosaraju solves this with finish times. Run a DFS over the whole graph and record the order in which vertices finish (a vertex finishes when all of its descendants are done). The key fact is:

If there is an edge from component C to a different component C', then the latest finish time inside C is larger than the latest finish time inside C'.

Why: if the DFS enters C' first, it cannot reach C from there (otherwise they would be one SCC), so all of C' finishes before C is even discovered. If the DFS enters C first at vertex x, then x stays on the stack until everything reachable from it, including all of C', has finished, so x finishes after every vertex of C'.

Consequently the vertex that finishes last sits in a source component of the condensation. Now reverse every edge. Reversal keeps the same SCCs (a cycle reversed is still a cycle) but turns sources into sinks. In the reversed graph, a DFS from the last-finished vertex is trapped inside its own component. After removing that component, the next unvisited vertex in decreasing finish order is again in a component whose only reversed-graph exits lead to components already removed, so the same argument repeats.

Algorithm.

  1. DFS the original graph from every unvisited vertex; push each vertex on a stack when it finishes.
  2. Build the transposed graph (every u → v becomes v → u).
  3. Clear visited. Pop vertices from the stack (largest finish time first). For each unvisited one, DFS the transposed graph; every vertex reached forms one SCC.
static List<List<Integer>> kosaraju(int V, int[][] edges) {
    List<List<Integer>> adj = buildAdj(V, edges);
    boolean[] visited = new boolean[V];
    Deque<Integer> finished = new ArrayDeque<>();          // top of the stack = vertex that finished last
    for (int u = 0; u < V; u++) {
        if (!visited[u]) dfsOrder(u, adj, visited, finished);
    }
    List<List<Integer>> rev = new ArrayList<>();
    for (int i = 0; i < V; i++) rev.add(new ArrayList<>());
    for (int[] e : edges) rev.get(e[1]).add(e[0]);         // transpose: u -> v becomes v -> u
    Arrays.fill(visited, false);
    List<List<Integer>> comps = new ArrayList<>();
    while (!finished.isEmpty()) {
        int u = finished.pop();
        if (visited[u]) continue;
        List<Integer> comp = new ArrayList<>();
        dfsCollect(u, rev, visited, comp);                 // everything reached here is exactly u's SCC
        comps.add(comp);
    }
    return normalise(comps);
}

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 only after all its descendants are done
}

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. The first pass starts at 0, goes 0 → 2 → 1 (the edge 1 → 0 leads back to a visited vertex), so 1 finishes, then 2; back at 0 it goes 0 → 3 → 4, so 4, 3 and finally 0 finish. The stack, top first, is 0, 3, 4, 2, 1. The reversed edges are 0→1, 2→0, 1→2, 3→0, 4→3.

Pop DFS on the reversed graph reaches Component
0 0, 1, 2 {0, 1, 2}
3 3 (its only reversed edge leads to the used vertex 0) {3}
4 4 (its only reversed edge leads to the used vertex 3) {4}
2, 1 already used none

Complexity. Time O(V + E): two DFS passes plus one pass to build the transpose. Space O(V + E) for the transposed graph, the finish stack and the visited array.

Approach 3: Kosaraju without recursion

Intuition. The recursive version nests one call per vertex on a path, so a chain of 10^5 vertices overflows Java’s default thread stack. The fix is to keep our own stack.

The second pass is easy: it only needs to know which vertices are reachable, not in what order, so a plain stack-based traversal works. The first pass is subtle. A typical iterative DFS pushes all neighbours at once, and that does not produce correct finish times. To finish a vertex only after all its descendants, we keep next[u], the index of the next neighbour of u to try. The vertex on top of the stack either advances to its next unvisited neighbour or, when it has none left, is popped and recorded as finished. That is exactly what the recursive call stack does.

static List<List<Integer>> kosarajuIterative(int V, int[][] edges) {
    List<List<Integer>> adj = buildAdj(V, edges);
    boolean[] visited = new boolean[V];
    int[] order = new int[V];                              // vertices in increasing finish time
    int[] next = new int[V];                               // next[u]: index of the next neighbour of u to try
    int finishedCount = 0;
    Deque<Integer> stack = new ArrayDeque<>();
    for (int s = 0; s < V; s++) {
        if (visited[s]) continue;
        visited[s] = true;
        stack.push(s);
        while (!stack.isEmpty()) {
            int u = stack.peek();
            if (next[u] < adj.get(u).size()) {
                int v = adj.get(u).get(next[u]++);
                if (!visited[v]) {
                    visited[v] = true;
                    stack.push(v);
                }
            } else {
                stack.pop();
                order[finishedCount++] = u;                // u finishes after all its descendants
            }
        }
    }
    List<List<Integer>> rev = new ArrayList<>();
    for (int i = 0; i < V; i++) rev.add(new ArrayList<>());
    for (int[] e : edges) rev.get(e[1]).add(e[0]);
    Arrays.fill(visited, false);
    List<List<Integer>> comps = new ArrayList<>();
    for (int i = V - 1; i >= 0; i--) {
        int s = order[i];
        if (visited[s]) continue;
        List<Integer> comp = new ArrayList<>();
        visited[s] = true;
        stack.push(s);
        while (!stack.isEmpty()) {
            int u = stack.pop();
            comp.add(u);
            for (int v : rev.get(u)) {
                if (!visited[v]) {
                    visited[v] = true;
                    stack.push(v);
                }
            }
        }
        comps.add(comp);
    }
    return normalise(comps);
}

Complexity. Same as Approach 2: O(V + E) time and space, with no risk of StackOverflowError. The Java file checks it on a single cycle through 100000 vertices.

Edge cases and pitfalls