Number of Connected Components
Understand the problem
Given an undirected graph with n nodes (numbered 0 to n-1) and a list of edges. Count the number of connected components in the graph.
Examples:
ts
n = 5, edges = [[0,1],[1,2],[3,4]]
output = 2
// Component 1: {0,1,2} — connected to each other
// Component 2: {3,4} — connected to each other
// An isolated node is also its own component
n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]
output = 1 // the whole graph is connectedEach DFS started from an unvisited node "eats" one whole connected component — the number of DFS calls = the number of components.
Basic approach
O(E × α(n)) time ≈ O(E) — α is the inverse Ackermann function, practically O(1)ts
// Simple Union-Find — intuitive for this problem
function countComponentsUF(n: number, edges: number[][]): number {
const parent = Array.from({ length: n }, (_, i) => i)
function find(x: number): number {
if (parent[x] !== x) parent[x] = find(parent[x])
return parent[x]
}
function union(x: number, y: number): boolean {
const px = find(x), py = find(y)
if (px === py) return false
parent[px] = py
return true
}
let components = n
for (const [a, b] of edges) {
if (union(a, b)) components--
}
return components
}Why this approach is slow:
Union-Find is very effective here but it adds another pattern to remember.
DFS with a visited array is simpler in an interview and also reaches O(V+E).
Unlock the optimal solution, the step-by-step trace and related questions
See the full step-by-step trace, Big-O and edge cases.