Data Structures / Graph algorithms / interactive lesson
Maintain connected components as a parent-pointer forest. Follow find operations to their representatives, watch path compression flatten expensive routes, and see union by rank keep trees shallow.
Disjoint-set timeline
Create 8 singleton sets
About the algorithm
Union-Find, also called Disjoint Set Union (DSU), maintains a changing partition of elements into non-overlapping sets. It quickly answers which representative owns an element and whether two elements already belong to the same connected component.
Disjoint-set forests were studied extensively in the 1960s and 1970s. Robert Tarjan proved the remarkable near-constant amortized complexity of combining path compression with rank-based linking. The structure became a standard tool for incremental connectivity.
Each set is stored as a rooted tree of parent pointers. find(x) walks to the root representative. union(a, b) finds two roots and links one below the other. Path compression rewires visited nodes directly to the root, while union by rank avoids unnecessary depth.
Union-Find powers Kruskal's minimum spanning tree algorithm, dynamic connectivity checks, image segmentation, maze generation, clustering, and equivalence-class processing. It is ideal when sets merge over time but never need to split.
Code companion
Connect each visual decision to an implementation pattern.
makeSet(n):
for each element x:
parent[x] = x
rank[x] = 0
find(x):
if parent[x] != x:
parent[x] = find(parent[x]) // path compression
return parent[x]
union(a, b):
rootA = find(a)
rootB = find(b)
if rootA == rootB: return
if rank[rootA] < rank[rootB]: swap(rootA, rootB)
parent[rootB] = rootA // union by rank
if rank[rootA] == rank[rootB]:
rank[rootA] += 1