A Union Find data structure (also called disjoint-set) is a data structure that keeps track of elements partitioned into a number of disjoint subsets. It provides near-constant-time operations to add new sets, to merge existing sets, and to determine whether elements are in the same set.
