Number of Connected Components in an Undirected Graph

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}