Union-Find (Disjoint-Set Union)

A near-constant-time structure that maintains a partition of elements into disjoint sets, supporting merge and same-set queries.

What it solves

The disjoint-set union (DSU) structure tracks a collection of elements grouped into non-overlapping sets. It answers two questions fast: which set does element x belong to (find), and merge the sets of x and y (union). It is the backbone of Kruskal's minimum spanning tree, connected-component labelling, and cycle detection in graphs.

Two optimizations

Kronos motion — confinement time

Each set is a rooted tree; the root is the set's representative. Union by rank/size attaches the smaller tree under the larger, bounding tree height. Path compression flattens the tree during find by repointing visited nodes directly at the root. Applied together, m operations on n elements run in O(m alpha(n)) time, where alpha is the inverse Ackermann function and is at most 4 for any practical input.

Reference implementation

python

parent = list(range(n))
rank = [0]*n

def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]  # path halving
        x = parent[x]
    return x

def union(a, b):
    ra, rb = find(a), find(b)
    if ra == rb:
        return False
    if rank[ra] < rank[rb]:
        ra, rb = rb, ra
    parent[rb] = ra
    if rank[ra] == rank[rb]:
        rank[ra] += 1
    return True

Extensions

Weighted DSU stores the offset of each node to its parent, letting you answer relative-value queries (used in equation-consistency checks). A rollback variant records unions on a stack so they can be undone, enabling DSU inside divide-and-conquer over time. DSU on a static graph gives offline connectivity queries after edge deletions by reversing them into insertions.

Complexity summary

Space O(n) for the parent and rank arrays.
Amortized O(alpha(n)) per find or union with both optimizations.
Path compression alone gives O(log n) amortized; union by rank alone gives O(log n) worst case.