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 and facilitates checking if two objects belong to the same set.
It provides near-constant-time operations to add new sets, to merge existing sets, and to 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 the Kruskal's algorithm to avoid forming cycles.
Resources
- Wikipedia Entry on Disjoint-set data structure.