Union by size
Always attach the smaller group under the bigger one's root, so no chain of parents ever grows long. About 10 minutes.
When chains get long
Imagine a company where every new hire reports to the previous boss's boss's boss. Finding the top of the chain gets slower with every hire.
Union-find can fall into the same trap. If every merge points the old leader at the newcomer, the pointer chains grow one step longer each time. Over 200,000 merges, just finding leaders adds up to billions of steps.
Small group joins the big one
The fix is to compare sizes before merging: the leader of the smaller group points to the leader of the bigger group, never the other way round.
That keeps every tree shallow. Each time a person's group is merged into a bigger one, their group at least doubles in size, and a group can only double about log n times before it contains everyone. So no chain ever gets long.
if size[ra] < size[rb]:
ra, rb = rb, ra
parent[rb] = ra- find(0) steps
- 3
Without sizes, each merge points the old leader at the newcomer: 0 to 1, then 1 to 2, then 2 to 3. Finding 0's leader now walks the whole chain, and every merge makes it longer.
A group of 5 and a group of 2 merge. With the small-under-big rule, whose leader points to whom?
- AThe group of 2's leader points to the group of 5's leader
- BThe group of 5's leader points to the group of 2's leader
Show the answer
The group of 2's leader points to the group of 5's leader. The smaller group moves under the bigger one, so the bigger tree doesn't get taller.
Merging computer clusters
A data center has n servers, numbered 0 to n - 1, each its own cluster. edges lists merge operations [a, b], in order, joining a and b's clusters. Return how many independent clusters remain once every merge in edges has happened.
n = 6, edges = [[0, 1], [2, 3], [1, 2], [4, 5]] → 2
1 ≤ n ≤ 200,000 · 0 ≤ edges.length ≤ 200,000 · edges[i] has two different node numbers, each 0 ≤ x < n