Strongly connected components (Kosaraju)
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
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;}