Union-find: which group is this in?
Union-find (disjoint-set union) tracks items split into non-overlapping groups and answers one question fast: are these two items in the same group? It supports two operations. find(x) returns the group's representative, its root. union(a, b) merges two groups by pointing one root at the other.
Each group is a small tree stored in a plain array of parent indexes. Two tricks keep the trees nearly flat: union by size (hang the smaller tree under the larger) and path compression (after a find, point every node on the path straight at the root). With both, each operation costs almost O(1) on average.
Merging customer records that share an email or a phone number into one person; finding which machines in a network can reach each other; detecting whether adding a road creates a loop (used in Kruskal's minimum spanning tree).
In code: Python · Rust
class DSU:
def __init__(self, n):
self.parent, self.size = list(range(n)), [1] * n
def find(self, x):
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # path halving
x = self.parent[x]
return x
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb: return False # already together
if self.size[ra] < self.size[rb]: ra, rb = rb, ra
self.parent[rb] = ra # smaller under larger
self.size[ra] += self.size[rb]
return Truestruct Dsu { parent: Vec<usize>, size: Vec<usize> }
impl Dsu {
fn new(n: usize) -> Self { Dsu { parent: (0..n).collect(), size: vec![1; n] } }
fn find(&mut self, mut x: usize) -> usize {
while self.parent[x] != x {
self.parent[x] = self.parent[self.parent[x]];
x = self.parent[x];
}
x
}
fn union(&mut self, a: usize, b: usize) -> bool {
let (mut ra, mut rb) = (self.find(a), self.find(b));
if ra == rb { return false; }
if self.size[ra] < self.size[rb] { std::mem::swap(&mut ra, &mut rb); }
self.parent[rb] = ra;
self.size[ra] += self.size[rb];
true
}
}- Path halving (shown) is a one-line form of path compression.
- Neither standard library has union-find; it's short enough that people write it from memory.