The problem
There are n nodes, numbered 0 to n − 1, and a list of undirected edges. Return the number of connected components — separate groups, where every node in a group can reach every other.
Examples
01
- Input
n = 5, edges = [[0, 1], [1, 2], [3, 4]]
- Output
2
02
- Input
n = 5, edges = [[0, 1], [1, 2], [2, 3], [3, 4]]
- Output
1
Constraints
- 1 ≤ n ≤ 2000
- 1 ≤ edges.length ≤ 5000
- No edge repeats.
The idea
Start with every node in a group of its own: n groups. Each edge either joins two different groups into one — one group fewer — or falls inside a group already joined, and changes nothing.
Union-find answers “same group?” and does the joining, each in almost constant time. The count left at the end is the answer.
- Time
- O(n + E · α(n))
- Space
- O(n)
Solution · every language run against every case
class Solution: def countComponents(self, n: int, edges: List[List[int]]) -> int: # Union-find: start with n groups; every edge that joins two groups makes one fewer. parent = list(range(n)) size = [1] * n def find(x): while parent[x] != x: parent[x] = parent[parent[x]] # halve the path as we go x = parent[x] return x groups = n for a, b in edges: ra, rb = find(a), find(b) if ra == rb: continue # already in one group if size[ra] < size[rb]: ra, rb = rb, ra parent[rb] = ra size[ra] += size[rb] groups -= 1 return groups