Track which elements belong to the same group, and merge groups together. Union Find (Disjoint Set Union) does both in nearly O(1) amortized time.
What Is It?
Union Find (also called Disjoint Set Union or DSU) manages a collection of non-overlapping sets. It supports two operations:
- Find(x): Which set does element x belong to? Returns the "representative" (root) of x's set.
- Union(x, y): Merge the sets containing x and y into one.