Union-Find Data Structure
A Union-Find data structure (a.k.a. Disjoint-set or Merge-find set data structure) categorizes objects into disjoint (non-overlapping) sets. It facilitates checking if two objects belong to the same set.
It provides near-constant-time operations to add new sets, merge existing sets, and determine whether elements are in the same set.
The most popular application of this data structure is to check whether one node in a graph can be reached from another, e.g., in Kruskal's algorithm, to avoid forming cycles.
Resources
- Wikipedia Entry on Disjoint-set data structure.