Union-Find

What union-find is

Union-Find (disjoint set union, DSU) maintains a collection of non-overlapping groups under two operations: find(x) - which group does x belong to - and union(x, y) - merge their groups. Each group is a tree of parent pointers whose root is the group's representative; two elements are connected exactly when their finds return the same root.

With two standard optimizations - path compression (during find, repoint every visited node at the root) and union by rank/size (attach the shorter tree under the taller) - both operations run in effectively constant amortized time (inverse Ackermann, below 5 for any input that fits in the universe).

How to recognize it

Signals: connectivity that CHANGES as edges arrive - 'are these connected after each merge', 'when does adding this edge create a cycle', 'how many groups remain', account/equivalence merging. The 'dynamic' part is the differentiator: on a static graph, DFS answers connectivity just as well; union-find shines when edges stream in and queries interleave.

Equivalence relations are the other tell: 'a == b and b == c implies a == c' - variable equality constraints, synonymous names, accounts sharing an email - all are union-find in disguise, sometimes with a hash map from strings to node ids in front.

The implementation

Two arrays: parent (initially parent[i] = i, everyone their own root) and rank (tree-height upper bound, initially 0). Find follows parents to the root, compressing on the way. Union finds both roots; if equal, the edge is internal (this is the cycle detector); otherwise attach lower rank under higher, incrementing rank only on ties. Track a component counter that decrements per successful union - 'number of groups' questions read it directly.

parent[i] = i for all i; rank[i] = 0; components = n

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

def union(x, y):
    rx, ry = find(x), find(y)
    if rx == ry: return false           # already connected (cycle!)
    if rank[rx] < rank[ry]: swap rx, ry
    parent[ry] = rx
    if rank[rx] == rank[ry]: rank[rx] += 1
    components -= 1
    return true

Complexity

m operations on n elements cost O(m x alpha(n)) with both optimizations - alpha is the inverse Ackermann function, effectively a constant. Space is O(n). Either optimization alone gives O(log n) amortized, still fine for interviews; using neither degrades to O(n) chains and is the classic silent performance bug.

Common pitfalls

Comparing parent[x] == parent[y] instead of find(x) == find(y) - parents are not roots except in fully compressed trees.

Skipping both optimizations: a sorted stream of unions builds a linked list and every find becomes O(n).

Forgetting that union returning false IS the cycle detection - re-deriving cycle checks with DFS next to a DSU is redundant.

String or coordinate elements: map them to integer ids first (hash map), or use a hash-map-keyed parent store.

Union-find handles merges only - there is no efficient 'un-union'. Deletion or time-travel questions need offline tricks or different structures; say so rather than improvising.

Worked examples

dsu = DSU(n)          # components = n
for i in 0 .. n-1:
    for j in i+1 .. n-1:
        if isConnected[i][j]:
            dsu.union(i, j)
return dsu.components

dsu = DSU(n)
for (u, v) in edges:
    if not dsu.union(u, v):     # already connected
        return (u, v)           # this edge closes the cycle

id = map email -> integer (assign on first sight)
owner = map email -> account name
for account in accounts:
    for email in account.emails[1:]:
        dsu.union(id[email], id[account.emails[0]])
groups = map root -> list of emails, via find(id[email])
return for each group: [owner name] + sorted emails

Check yourself

Try to answer before revealing - retrieving from memory is what makes it stick.

Frequently asked questions