Strongly Connected Components (Kosaraju's Algorithm)

Hard
1681.

Strongly Connected Components (Kosaraju's Algorithm)

Strongly Connected Components (Kosaraju's Algorithm) is a hard coding problem on depth-first search and graph, asked in Amazon, Microsoft, Adobe and Flipkart interviews.

You are given a directed graph with n vertices numbered 0 to n - 1; each edges[i] = [u, v] is an edge from u to v.

Two vertices belong to the same strongly connected component when each can reach the other along directed edges. Every vertex lies in exactly one component (a vertex alone is a component of size one).

Return the number of strongly connected components.

Example 1

Input
n = 5, edges = [[0,2],[2,1],[1,0],[0,3],[3,4]]
Output
3
Explanation
The components are {0, 1, 2}, {3} and {4}.

Example 2

Input
n = 3, edges = [[0,1],[1,2],[2,0]]
Output
1
Explanation
The three edges form one cycle, so every vertex reaches every other.

Example 3

Input
n = 4, edges = [[0,1],[1,2],[2,3]]
Output
4
Explanation
A path has no way back, so each vertex is its own component.

Constraints

  • 1 <= n <= 5000
  • 0 <= edges.length <= 10^4
  • edges[i].length == 2
  • 0 <= u, v < n, u != v
  • there are no repeated edges
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number}
 */
var kosaraju = function(n, edges) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Strongly Connected Components (Kosaraju's Algorithm) Solution

Strongly Connected Components (Kosaraju's Algorithm) solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Strongly Connected Components (Kosaraju's Algorithm) is a hard coding problem on depth-first search and graph, asked in Amazon, Microsoft, Adobe and Flipkart interviews.

Problem statement

You are given a directed graph with n vertices numbered 0 to n - 1; each edges[i] = [u, v] is an edge from u to v.

Two vertices belong to the same strongly connected component when each can reach the other along directed edges. Every vertex lies in exactly one component (a vertex alone is a component of size one).

Return the number of strongly connected components.

Example 1

Input: n = 5, edges = [[0,2],[2,1],[1,0],[0,3],[3,4]]
Output: 3
Explanation: The components are {0, 1, 2}, {3} and {4}.

Example 2

Input: n = 3, edges = [[0,1],[1,2],[2,0]]
Output: 1
Explanation: The three edges form one cycle, so every vertex reaches every other.

Example 3

Input: n = 4, edges = [[0,1],[1,2],[2,3]]
Output: 4
Explanation: A path has no way back, so each vertex is its own component.

Constraints

  • 1 <= n <= 5000
  • 0 <= edges.length <= 10^4
  • edges[i].length == 2
  • 0 <= u, v < n, u != v
  • there are no repeated edges

Hints for Strongly Connected Components (Kosaraju's Algorithm)

  1. Hint 1

    If you start a DFS inside a "sink" component — one with no edges leaving it — the DFS visits exactly that component.

  2. Hint 2

    In a first DFS, record vertices in order of finishing time. The vertex that finishes last lies in a source component of the condensation.

  3. Hint 3

    Reverse every edge: sources become sinks. Run DFS on the reversed graph in decreasing finishing time; each new start discovers one whole component.

How to solve Strongly Connected Components (Kosaraju's Algorithm)

Kosaraju's algorithm uses two depth-first searches. The first orders vertices by finishing time; the second, on the transposed graph and in reverse finishing order, peels off one strongly connected component per DFS tree.

Approach

  1. Build the adjacency list g and its transpose rg (every edge reversed).
  2. DFS over g from every unvisited vertex, appending each vertex to order when it finishes.
  3. Clear the visited marks. Walk order from last to first; whenever a vertex is unvisited, count a new component and DFS from it over rg, marking everything reached.
  4. Return the count.

Why it works

For two components C and D with an edge from C to D, the latest finishing time in C exceeds every finishing time in D. So the vertex taken first in the second pass belongs to a source component of the condensation — which is a sink in the transpose — and a DFS on rg from it cannot leave its component. Its component is then removed and the argument repeats on what remains.

Complexity

  • Time — O(n + E)
  • Space — O(n + E)

Pitfalls

  • The second pass must run on the reversed graph; running it on g merges components.
  • Use finishing order, not discovery order.
  • Isolated vertices are components too — loop over every vertex, not just those that appear in an edge.

Reference solution

Python

import sys
from typing import List

def kosaraju(n: int, edges: List[List[int]]) -> int:
    sys.setrecursionlimit(max(1000, 4 * n + 100))
    g = [[] for _ in range(n)]
    rg = [[] for _ in range(n)]
    for u, v in edges:
        g[u].append(v)
        rg[v].append(u)
    seen = [False] * n
    order = []

    def dfs1(u):
        seen[u] = True
        for v in g[u]:
            if not seen[v]:
                dfs1(v)
        order.append(u)

    def dfs2(u):
        seen[u] = True
        for v in rg[u]:
            if not seen[v]:
                dfs2(v)

    for u in range(n):
        if not seen[u]:
            dfs1(u)
    for u in range(n):
        seen[u] = False
    count = 0
    for u in reversed(order):
        if not seen[u]:
            count += 1
            dfs2(u)
    return count

Java

public static int kosaraju(int n, int[][] edges) {
    List<List<Integer>> 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]); }
    boolean[] seen = new boolean[n];
    List<Integer> order = new ArrayList<>();
    for (int u = 0; u < n; u++) if (!seen[u]) sccFirst(g, u, seen, order);
    seen = new boolean[n];
    int count = 0;
    for (int t = order.size() - 1; t >= 0; t--) {
        int u = order.get(t);
        if (!seen[u]) { count++; sccSecond(rg, u, seen); }
    }
    return count;
}

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

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

C++

static void sccFirst(vector<vector<int>>& g, int u, vector<bool>& seen, vector<int>& order) {
    seen[u] = true;
    for (int v : g[u]) if (!seen[v]) sccFirst(g, v, seen, order);
    order.push_back(u);
}

static void sccSecond(vector<vector<int>>& rg, int u, vector<bool>& seen) {
    seen[u] = true;
    for (int v : rg[u]) if (!seen[v]) sccSecond(rg, v, seen);
}

int kosaraju(int n, vector<vector<int>>& edges) {
    vector<vector<int>> g(n), rg(n);
    for (auto& e : edges) { g[e[0]].push_back(e[1]); rg[e[1]].push_back(e[0]); }
    vector<bool> seen(n, false);
    vector<int> order;
    for (int u = 0; u < n; u++) if (!seen[u]) sccFirst(g, u, seen, order);
    seen.assign(n, false);
    int count = 0;
    for (int t = (int)order.size() - 1; t >= 0; t--) {
        if (!seen[order[t]]) { count++; sccSecond(rg, order[t], seen); }
    }
    return count;
}

JavaScript

var kosaraju = function(n, edges) {
    var g = [], rg = [], seen = [], order = [];
    for (var i = 0; i < n; i++) { g.push([]); rg.push([]); seen.push(false); }
    for (var k = 0; k < edges.length; k++) { g[edges[k][0]].push(edges[k][1]); rg[edges[k][1]].push(edges[k][0]); }
    var dfs1 = function(u) {
        seen[u] = true;
        for (var j = 0; j < g[u].length; j++) if (!seen[g[u][j]]) dfs1(g[u][j]);
        order.push(u);
    };
    var dfs2 = function(u) {
        seen[u] = true;
        for (var j = 0; j < rg[u].length; j++) if (!seen[rg[u][j]]) dfs2(rg[u][j]);
    };
    for (var u = 0; u < n; u++) if (!seen[u]) dfs1(u);
    for (var x = 0; x < n; x++) seen[x] = false;
    var count = 0;
    for (var t = order.length - 1; t >= 0; t--) {
        if (!seen[order[t]]) { count++; dfs2(order[t]); }
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Graph Data Structure