Basic Operations in DSU
Thus the basic implementation of the DSU data structure consists of only three operations:
- Creation of Disjoint Sets [make_set(v)] – creates a new set consisting of the new element v
- Union of Sets [union_sets(a, b)] – merges the two specified sets (the set in which the element a is located, and the set in which the element b is located)
- Find in Disjoint Sets [find_set(v)] – returns the representative (also called leader) of the set that contains the element ‘v’. This representative is an element of its corresponding set. It is selected in each set by the data structure itself (and can change over time, namely after union_sets calls). This representative can be used to check if two elements are part of the same set or not. ‘a‘ and ‘b‘ are exactly in the same set, if find_set(a) == find_set(b). Otherwise they are in different sets.