Improvement 2 - Union by Size

When you merge two groups, which one should become the child? It is smarter to attach the smaller tree under the larger tree. This keeps the combined tree shallow.

Track size of each group in a size array. When unioning, make the smaller group's root point to the larger group's root. Update the larger group's size.

With union by size (or rank), tree height stays $O(\log n)$. Combined with path compression, operations become $O(\alpha(n))$ amortized, where $\alpha$ is the inverse Ackermann function, effectively constant.

Space complexity is $O(n)$ for the data structures used.