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 element
Union(x,y)merges the two (disjoint) sets whose representatives are
Find(x)returns the representative of the set which contains
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).