data-structures Union-find data structure Improvements: Union by size
Example
In our current implementation of merge, we always choose the left set to be the child of the right set, without taking the size of the sets into consideration. Without this restriction, the paths (without path compression) from an element to its representative might be quite long, thus leading to large runtimes on find calls.
Another common improvement thus is the union by size heuristic, which does exactly what it says: When merging two sets, we always set the larger set to be the parent of the smaller set, thus leading to a path length of at most 
steps:
We store an additional member std::vector<size_t> size in our class which gets initialized to 1 for every element. When merging two sets, the larger set becomes the parent of the smaller set and we sum up the two sizes:
private:
...
std::vector<size_t> size;
public:
union_find(size_t n) : parent(n), size(n, 1) { ... }
...
void merge(size_t i, size_t j) {
size_t pi = find(i);
size_t pj = find(j);
if (pi == pj) { // If the elements are in the same set:
return; // do nothing
}
if (size[pi] > size[pj]) { // Swap representatives such that pj
std::swap(pi, pj); // represents the larger set
}
parent[pi] = pj; // attach the smaller set to the larger one
size[pj] += size[pi]; // update the size of the larger set
}
