data-structures Union-find data structure Improvements: Path compression
Example
If we do many merge operations on a union-find data structure, the paths represented by the parent pointers might be quite long. Path compression, as already described in the theory part, is a simple way of mitigating this issue.
We might try to do path compression on the whole data structure after every k-th merge operation or something similar, but such an operation could have a quite large runtime.
Thus, path compression is mostly only used on a small part of the structure, especially the path we walk along to find the representative of a set. This can be done by storing the result of the find operation after every recursive subcall:
size_t find(size_t i) const {
if (parent[i] == i) // If we already have a representative
return i; // return it
parent[i] = find(parent[i]); // path-compress on the way to the representative
return parent[i]; // and return it
}
