When we compute a given set of elements, it is often useful to break them up or partition them into a number of separate.
A Union-Find data structure maintains a partition of a set X of size n. For each set A in the partition it maintains a representative S(A) contained in A. The initial partition has each element in a set by itself. Operations include Union(S(A), S(B)), where S(A) =6 S(B), replaces A and B by A ∪ B, and speciļ¬es a representative for A ∪ B.
A union-find algorithm is an algorithm that performs two useful operations on such a data structure:
- Find: Determine which set a particular element is in. Also useful for determining if two elements are in the same set.
- Union: Combine or merge two sets into a single set.
Because it supports these two operations, a disjoint-set data structure is sometimes called a union-find data structure or merge-find set. The other important operation, MakeSet, which makes a set containing only a given element a singleton, is generally trivial. With these three operations, many practical partitioning problems can be solved.
