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:
MakeSet(x)creates a new set with a single elementx.Union(x,y)merges the two (disjoint) sets whose representatives arexandy, respectively.Find(x)returns the representative of the set which containsx.
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 data-structures (if the question is about union-find data structures themselves) or algorithms (if it is about using union-find in an algorithm).
