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 maintains a few structures:

• The array link[] contains for each element, the next element in the chain. At the beginning of the chain, the link[i] contains i.
  • We initialise the ith element in the array with value 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.
  • Note that two elements are only in the same group if they have the same representatives, i.e., their find() results are the same.
  • Path compression is a simple optimisation. Instead of recursively finding the representative element of the set (with $O(\log n)$), we can point the parent directly to the representative element, such that it’ll have $O(\alpha (n))$ (the inverse Ackermann function).
• 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.

Competitive programming

We can use union find primarily for finding the number of graphs contained in an input. In C++, we have:

class UnionFind {
	private:
		vector<int> parent;
		vector<int> size;
	public:
		UnionFind(int n) {
			parent.resize(n);
			size.resize(n, 1);
			for (int i = 0; i < n; i++) {
				parent[i] = i; // default init
			}
		}
 
		int find(int x) {
			if (parent[x] != x) {
				parent[x] = find(parent[x]);
			}
			return parent[x];
		}
 
		int unite(int x, int y) {
			int root_x = find(x);
			int root_y = find(y);
 
			if (root_x != root_y) {
				parent[root_y] = root_x;
				size[root_x] += size[root_y];
			}
		}
 
		int get_size(int x) {
			return size[find(x)];
		}
};