Union-Find

The union-find structure tracks a partition into disjoint sets, answering connectivity queries in near-constant amortized time.

Disjoint sets

Union-find, also called a disjoint-set structure, maintains a collection of elements partitioned into non-overlapping sets. It supports two operations: find, which returns a representative identifying the set an element belongs to, and union, which merges two sets. Two elements are in the same set exactly when their finds return the same representative.

Forest of parent pointers

Kronos motion — confinement time

Each set is stored as a tree where every node points to a parent and the root is the representative. Find walks parent pointers to the root; union links one root under another. On its own this can degrade to O(n) chains, so two optimisations are applied together.

Union by rank: attach the shorter tree under the taller to keep trees flat
Path compression: during find, repoint visited nodes straight to the root

Near-constant time

With both optimisations, any sequence of m operations on n elements runs in O(m alpha(n)), where alpha is the inverse Ackermann function. That function grows so slowly it is below five for any conceivable input, so each operation is effectively constant time.

python

def find(p, x):
    while p[x] != x:
        p[x] = p[p[x]]   # path compression
        x = p[x]
    return x

def union(p, r, a, b):
    ra, rb = find(p, a), find(p, b)
    if ra == rb: return
    if r[ra] < r[rb]: ra, rb = rb, ra
    p[rb] = ra
    if r[ra] == r[rb]: r[ra] += 1

What it cannot do

Union-find supports merging sets and testing membership, but it does not support splitting a set back apart: once merged, sets stay merged. Problems that require deletion or un-merging need a different structure or an offline technique that processes operations in reverse. This one-way nature is the price of its near-constant speed.

Where it is used

Union-find powers Kruskal's minimum-spanning-tree algorithm, where it detects whether adding an edge would form a cycle. It also drives connected-component labelling, network-connectivity queries, image segmentation, and cycle detection in undirected graphs. Whenever you must repeatedly merge groups and ask whether two things are connected, it is the right tool.