Union find

Disjoint sets are a data structure that extends the functionality of sets by maintaining multiple disjoint subsets of elements, i.e., a disjoint set with two subsets $A,B$ have:

$$A\cap B=\varnothing$$

These find considerable use in graph problems, especially in applying the basic union and find operations (union-find algorithm).

Union-find

Union-find maintains a few structures:

• The array link[] contains for each element, the next element in the chain. At the beginning, the link[i] contains i.
• The array size[] contains the size of each subset, given the i-th element.

There are also two main functions:

• The find() algorithm returns the representative for an element x, which can be found by following the chain that begins at x.
• The unite() function joins the initially disjoint sets that contains elements $a$ and $b$. It finds the representatives of the subsets, then connects the smaller set to the larger set.