Are these two connected?
A social network adds friendships one at a time. At any moment you want to answer: are Ana and Raj in the same circle, through any chain of friends?
You could search the whole network each time. With millions of people and millions of questions, that is far too slow.
Union-find (also called a disjoint set) is built for exactly this. It supports two operations, and both are close to instant:
- union(a, b): a and b are now connected, so merge their groups.
- find(a): which group is a in?
Two items are connected when find gives the same answer for both.
The idea: every group has a root
Each item points at one other item
Think of an arrow from each item to its "parent".
Follow the arrows and you reach the root
The root is the one item in a group that points at itself. It acts as the name of the group.
find(a) means: walk from a to its root
Two items with the same root are in the same group.
union(a, b) means: point one root at the other
One arrow changes, and two whole groups become one.
The whole structure is one array: who each item points at
Start. Eight items, each in a group of one. Every item points at itself, which means: I am the root of my group.
- Groups
- 8
- Hops in last find
- 0
All of it is stored in a single array: for each item, who it points at.
Two tricks that keep it fast
Left alone, the trees could grow into long chains, and a long chain means a slow walk to the root. Two small habits prevent that.
Hang the smaller tree under the larger. When merging, the root of the smaller group points at the root of the larger. The tall tree does not get taller.
Path compression. While walking from an item to the root, you pass several items. They all share that root. So on the way back, point each of them straight at it. The next time anyone asks about them, the answer is one hop away.
Example
Before and after one find
In the animation, G points at E and E points at A. Finding G's root takes two hops. Afterwards G points directly at A, and the same question takes one hop. On a long chain the saving is much larger: every item on the path is moved next to the root in one go.
parent = list(range(n)) # everyone starts as their own root
size = [1] * n
def find(a):
if parent[a] != a:
parent[a] = find(parent[a]) # path compression
return parent[a]
def union(a, b):
root_a, root_b = find(a), find(b)
if root_a == root_b:
return # already in the same group
if size[root_a] < size[root_b]:
root_a, root_b = root_b, root_a
parent[root_b] = root_a # smaller tree goes under the larger
size[root_a] += size[root_b]
def connected(a, b):
return find(a) == find(b)With both tricks, a long series of operations costs so close to one step each that the difference does not matter in practice.
What it cannot do
Good at
- Merging groups and asking "same group?" are both nearly instant
- Just two small arrays, and a dozen lines of code
Where it bites
- Groups can be merged but not split apart again
- It tells you whether two items are connected, not the path between them
Where you will meet it
- Networks: which computers can reach each other as cables are added.
- Building a cheapest network: Kruskal's algorithm adds the cheapest links one by one and uses union-find to skip any link that would join two points already connected.
- Images: grouping neighbouring pixels of the same colour into regions.
Key takeaways
- Union-find tracks which items are in the same group as connections are added.
- Each item points at a parent. Following the arrows leads to the group's root.
- Union points one root at another. Find walks to the root.
- Merging small under large, and flattening paths during find, keep the trees very short.
- It answers "are they connected?", not "how?", and it cannot undo a merge.