HowToCodePage

Union-Find and disjoint sets

The parent array, union by rank and path compression, why the amortised cost is nearly constant, and the cycle detection and clustering patterns it powers.

A forest in an array

Union-Find tracks which elements belong to the same group. Each element points at a parent; the root of a tree is the group's representative. Two elements are in the same set when they share a root.

parent = list(range(n))    # every element starts as its own root
rank   = [0] * n           # upper bound on subtree height

def find(x):
    root = x
    while parent[root] != root:      # walk to the root
        root = parent[root]
    while parent[x] != root:         # path compression: flatten the chain
        parent[x], x = root, parent[x]
    return root

def union(a, b):
    ra, rb = find(a), find(b)
    if ra == rb:
        return False                 # already together: cycle detected
    if rank[ra] < rank[rb]:
        ra, rb = rb, ra
    parent[rb] = ra                  # attach the shorter tree under the taller
    if rank[ra] == rank[rb]:
        rank[ra] += 1
    return True

Why it is effectively constant

OptimisationUnion costFind costNote
NoneO(1)O(n) worst caseA long chain of parents
Union by rank onlyO(log n)O(log n)Height stays logarithmic
Path compression onlyO(log n) amortisedO(log n) amortisedFlattens on access
BothO(alpha(n))O(alpha(n))Alpha is under 5 for any real n

The inverse Ackermann function grows so slowly that for any input that fits in memory the cost is a small constant. Union-Find is the standard example of an amortised bound that is better than the naive worst case by a huge margin.

# counting groups after a series of unions
groups = len({find(i) for i in range(n)})

# largest component size
from collections import Counter
sizes = Counter(find(i) for i in range(n))
largest = max(sizes.values())

What you build with it

  • Kruskal's algorithm — sort edges by weight and union the endpoints; union returning false means the edge would close a cycle, so skip it.
  • Cycle detection in an undirected graph, with no graph traversal at all.
  • Connected components in a dynamic graph where edges are only added.
  • Clustering and segmentation — merge pixels or records until a threshold stops the merging.
  • Account or entity resolution — union records that share an email or phone number.
def kruskal(n, edges):
    edges.sort(key=lambda e: e[2])       # by weight
    return [e for e in edges if union(e[0], e[1])]
💡
Union-Find only supports merging. There is no split operation, and no way to undo a union without rebuilding. If your problem needs deletion or rollback, you need a different structure such as a dynamic connectivity tree.

FAQ

Can I use Union-Find with string keys?
Map the strings to integer indices once, then work on the integers. The structure is array-based by design, and adding a dictionary lookup inside find would destroy its performance.
What is the difference between rank and size?
Both are valid heuristics. Union by size attaches the smaller set under the larger by element count; rank uses the height. Rank is slightly cheaper to maintain and gives the same bound.

Graphs and their representations LRU caches and composite structures

Last refreshed 2026-09-18.