Questions about the abstract data structure Union-Find (also called disjoint-set) and its realizations.

Union-Find or disjoint-set is characterised by three operations:

  1. MakeSet(x) creates a new set with a single element x.
  2. Union(x,y) merges the two (disjoint) sets whose representatives are x and y, respectively.
  3. Find(x) returns the representative of the set which contains x.

Some problems can be solved by using only these operations (which are notably less powerful than full-blown sets or dictionaries). One popular example is Kruskal's algorithm for finding minimal spanning trees. Such algorithms profit from the efficient implementations we have for Union-Find.

Questions tagged with this tag should probably also have (if the question is about union-find data structures themselves) or (if it is about using union-find in an algorithm).

history | excerpt history