Pointer Walk

Union-Find

Are these two connected? Ask the root. Path compression flattens the trees so later questions take one hop.

Data StructuresIntermediate9 min read

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

  1. Each item points at one other item

    Think of an arrow from each item to its "parent".

  2. 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.

  3. find(a) means: walk from a to its root

    Two items with the same root are in the same group.

  4. union(a, b) means: point one root at the other

    One arrow changes, and two whole groups become one.

Union-find: merging groupsInteractive
ABCDEFGH

The whole structure is one array: who each item points at

AA
BB
CC
DD
EE
FF
GG
HH

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.

python
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.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    7 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress