Union Find — How the Pattern Works
Union-Find (Disjoint Set Union, or DSU) is a forest-based data structure that partitions elements into disjoint connected components while supporting dynamic merges and connectivity queries. Each component maintains a rooted tree invariant where a canonical representative (parent[root] == root) uniquely identifies the set, allowing two sets to merge by redirecting a single root pointer rather than relabeling elements. Combined with path compression and union by size/rank, both find and union execute in amortized O(α(n)) (effectively O(1)) time, reducing repeated O(V + E) graph traversals or O(n^2) component scans to near-linear complexity.
- Edges or elements arrive incrementally and the problem asks for dynamic connectivity, live component counts, or the exact edge that first closes a cycle.
- Items are grouped transitively by a pairwise equivalence relation (shared row/column, shared email key, single-swap string similarity, or consecutive integer adjacency).
- Minimum Spanning Tree construction (Kruskal's algorithm) where weighted edges (and virtual source edges) are processed cheapest-first and cycle-forming edges must be skipped.
- Grid cells or graph paths progressively split apart over time (e.g., daily flooding), allowing offline time reversal so splits turn into incremental Union-Find merges.
- Pairwise multiplicative ratios link variables across equations (weighted Union-Find), or painted coordinate intervals must skip already-processed slots (
next_freejump pointers).
- Comparing
parent[a] == parent[b]instead offind(a) == find(b):parent[x]can still point to an intermediate ancestor before path compression runs, causing false negatives on connectivity checks. - Writing
parent[b] = ainstead ofparent[find(b)] = find(a)duringunion: overwriting a non-root node's parent detaches it from its existing component and corrupts component connectivity. - Updating
size[ra] += size[rb]or decrementingcomponents -= 1without checkingra != rb: merging two nodes already in the same component inflates component sizes and undercounts remaining groups. - Attempting to split components directly in standard Union-Find: DSU does not invert past merges, so problems where connectivity breaks over time must be processed offline in reverse chronological order.
parent, size = list(range(n)), [1] * n
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(a, b):
ra, rb = find(a), find(b)
if ra != rb:
if size[ra] < size[rb]: ra, rb = rb, ra
parent[rb] = ra
size[ra] += size[rb]
return ra != rbparent = {}
def find(x):
parent.setdefault(x, x)
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(a, b):
ra, rb = find(a), find(b)
if ra != rb:
parent[rb] = raparent, ratio = {}, {}
def find(x):
if parent[x] != x:
old = parent[x]
parent[x] = find(old)
ratio[x] *= ratio[old]
return parent[x]
def union(a, b, val):
ra, rb = find(a), find(b)
if ra != rb:
parent[ra] = rb
ratio[ra] = val * ratio[b] / ratio[a]