Intro to union-find

Union-Find (Disjoint Set Union)

Union-Find (also called Disjoint Set Union, DSU) tracks a collection of elements partitioned into disjoint groups, and answers two questions fast:

find(x) — which group is x in? (return a representative)
union(x, y) — merge the groups containing x and y.

It's the natural tool for "are these connected?" and "how many groups are there?" as connections arrive incrementally.

The array representation

Each element points to a parent; following parents leads to the group's root (representative). Initially every element is its own parent (n singleton groups).

parent = new array of size n
for i in 0..n-1: parent[i] = i

function find(x):
    while parent[x] != x:
        x = parent[x]
    return x

function union(a, b):
    parent[find(a)] = find(b)

Two elements are in the same group iff find(a) == find(b).

Making it fast

The naive version above can build tall, skinny trees, making find slow. Two optimisations together make operations nearly O(1) (amortised, inverse-Ackermann):

Path compression — during find, repoint every node you pass directly to the root, so future finds on them are one hop:

function find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]   // point x at its grandparent (flattens the tree)
        x = parent[x]
    return x

Union by size — keep a size[] per root and always attach the smaller tree under the larger, so trees stay shallow:

size = new array of size n
for i in 0..n-1: size[i] = 1

function union(a, b):
    ra, rb = find(a), find(b)
    if ra == rb: return
    if size[ra] < size[rb]:         // attach smaller under larger
        ra, rb = rb, ra
    parent[rb] = ra
    size[ra] += size[rb]

(Union by rank — tracking tree height instead of node count — works the same way.) With both optimisations, a sequence of m operations costs effectively O(m).

Where it shines

Counting connected components as edges are added.
Kruskal's minimum-spanning-tree algorithm.
"Number of provinces", "redundant connection", "accounts merge".

Union-Find trades the generality of BFS/DFS for blazing-fast incremental connectivity. The next two problems have you build it, then use it.