Connected groups (union-find)
We'll cover the following
Edges connect nodes. After adding all edges, how many separate groups exist?
Watch it run
Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.
00
11
22
33
44
55
66
77
88
99
1010
1111
1212
1313
Each node starts as its own group: parent[i] = i.
groups 14
1 / 15
The idea
Complexity
| Time | Space | Why |
|---|---|---|
O(E α(V)) | O(V) | With path compression each find is almost constant. |
In Python
def count_groups(n, edges):
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path compression
x = parent[x]
return x
groups = n
for u, v in edges:
ru, rv = find(u), find(v)
if ru != rv: parent[ru] = rv; groups -= 1
return groupsSummary: say it in the interview
- Keep a parent array. find(x) climbs to the root. For each edge, if the two roots differ, point one root at the other and the group count drops by one. Two nodes are connected exactly when they share a root.
- Time O(E α(V)), space O(V). With path compression each find is almost constant.