Union-Find Algorithm
A data structure for efficiently tracking and merging disjoint sets of elements
Union-Find (also called Disjoint-Set Union or DSU) is a data structure that efficiently tracks a collection of disjoint sets, supporting two core operations: finding which set an element belongs to, and merging two sets together.
Definition
Union-Find (also called Disjoint-Set Union or DSU) is a data structure that efficiently tracks a collection of disjoint sets, supporting two core operations: finding which set an element belongs to, and merging two sets together.
Overview
Union-Find solves a deceptively simple problem: given elements that get grouped and regrouped into sets over time, quickly answer "are these two elements in the same group?" and "merge these two groups into one." A naive implementation, where each element stores a direct pointer to its group, makes union operations expensive because merging two large groups requires updating every element in one of them. Union-Find instead represents each set as a tree, where each element points to a parent, and the root of the tree serves as that set's representative; two elements are in the same set exactly when they share the same root. Two optimizations turn this simple idea into one of the most efficient data structures in computer science. Union by rank (or by size) always attaches the smaller or shallower tree under the root of the larger one during a union, preventing trees from becoming needlessly tall. Path compression flattens the tree during a find operation by making every node on the path point directly to the root, so future lookups for those same elements become instant. Applied together, these two optimizations give an amortized time complexity per operation of O(α(n)), where α is the inverse Ackermann function — a function that grows so slowly it's effectively a small constant (less than 5) for any input size that could exist in practice. Union-Find is the standard implementation behind Kruskal's algorithm for finding a minimum spanning tree, where it efficiently detects whether adding an edge would create a cycle. It also shows up in image processing for connected-component labeling, in network connectivity problems, in compiler optimizations for tracking equivalent variables, and in puzzles like detecting cycles in an undirected graph or counting the number of connected components. Its combination of conceptual simplicity and near-constant-time performance makes it a frequent subject in both algorithms coursework and technical interviews.
Key Concepts
- Two core operations: find (which set does an element belong to) and union (merge two sets)
- Represents sets as trees, with each set's root as its representative element
- Union by rank/size keeps trees shallow by attaching smaller trees under larger ones
- Path compression flattens trees during find for faster future lookups
- Combined optimizations give amortized O(α(n)) time per operation
- α(n), the inverse Ackermann function, is effectively constant for all practical input sizes
- Core building block of Kruskal's minimum spanning tree algorithm
- Simple to implement with just an array of parent pointers