UnionFind

UnionFind, also known as Disjoint Set Union (DSU), is a data structure that maintains a partition of a set into disjoint subsets. It supports two primary operations: find(x), which returns the representative or root of the set containing x, and union(x, y), which merges the sets containing x and y into a single set. A common auxiliary function is connected(x, y), which tests whether x and y belong to the same set. The structure represents each set as a tree, with each node pointing to a parent and the root serving as the set representative.

Typical implementation uses two arrays: parent and rank (or size). Initially, each element is its own parent, forming singleton sets. The find operation uses path compression: during traversal to the root, each visited node is directly attached to the root, flattening the tree. The union operation uses union by rank (or by size): after finding the roots, the root of the smaller tree is attached to the root of the larger one, and the rank/size of the resulting root is updated accordingly. This keeps the trees shallow and improves efficiency.

Time complexity is nearly linear in practice. Each operation runs in amortized inverse Ackermann time, α(n), which is effectively a constant for any realistic input. Memory usage is O(n). Common applications include Kruskal’s algorithm for minimum spanning trees, flood-fill or connectivity queries in offline dynamic graphs, image segmentation, and network connectivity checks.

Limitations include difficulty supporting deletions; dynamic connectivity with removals requires more advanced variants. UnionFind remains a foundational tool for efficiently tracking connected components.