Number of Connected Components in an Undirected Graph
Problem
Given n nodes labelled 0..n−1 and a list of undirected edges, return the number of connected components.
Example 1
Input: n = 5, edges = [[0,1], [1,2], [3,4]] Output: 2
Test cases
Case 1
Input: 5, [[0,1],[1,2],[3,4]] Expected: 2
Case 2
Input: 5, [[0,1],[1,2],[2,3],[3,4]] Expected: 1
Case 3
Input: 3, [] Expected: 3
View solutionHide solution2 approaches
1. DFS from each unvisited node
Time O(V + E)Space O(V + E)
Each DFS start is a new component.
function countComponents(n, edges) { const adj = Array.from({ length: n }, () => []); for (const [a, b] of edges) { adj[a].push(b); adj[b].push(a); } const seen = new Array(n).fill(false); const dfs = (u) => { seen[u] = true; for (const v of adj[u]) if (!seen[v]) dfs(v); }; let count = 0; for (let i = 0; i < n; i++) if (!seen[i]) { count++; dfs(i); } return count;}2. Union-Find
Time O(E · α(n))Space O(n)
Start with n components; every successful union merges two, so subtract one.
function countComponents(n, edges) { const parent = [...Array(n).keys()]; const find = (x) => (parent[x] === x ? x : (parent[x] = find(parent[x]))); let count = n; for (const [a, b] of edges) { const ra = find(a), rb = find(b); if (ra !== rb) { parent[ra] = rb; count--; } } return count;}