Strongly connected components (Kosaraju)

Hard

Problem

In a directed graph, a strongly connected component is a maximal set of nodes where every node can reach every other. Count (or list) the SCCs.

Example 1

Input:  edges 1→0, 0→2, 2→1, 0→3, 3→4
Output: 3 SCCs: {0, 1, 2}, {3}, {4}

Also asked as: Count Strongly connected Components(Kosaraju Algo)

Test cases

Case 1

Input:    5, [[2,3],[0],[1],[4],[]]
Expected: 3

Case 2

Input:    3, [[1],[2],[0]]
Expected: 1

Case 3

Input:    2, [[1],[]]
Expected: 2

Case 4

Input:    3, [[],[],[]]
Expected: 3

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Two passes: finish-time order, then DFS the transpose

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

1) DFS the graph pushing nodes on a stack by finish time. 2) DFS the reversed graph in that stack order — each tree is one SCC.

function kosaraju(n, adj) {
const radj = Array.from({ length: n }, () => []);
for (let u = 0; u < n; u++) for (const v of adj[u]) radj[v].push(u);
const seen = new Array(n).fill(false), order = [];
const dfs1 = (u) => { seen[u] = true; for (const v of adj[u]) if (!seen[v]) dfs1(v); order.push(u); };
for (let i = 0; i < n; i++) if (!seen[i]) dfs1(i);
seen.fill(false);
let count = 0;
const dfs2 = (u) => { seen[u] = true; for (const v of radj[u]) if (!seen[v]) dfs2(v); };
for (let i = order.length - 1; i >= 0; i--) if (!seen[order[i]]) { dfs2(order[i]); count++; }
return count;
}