A path-compressed Quick Union is a Quick Union where, each time the root node of an element is found, it’s parent pointer is set to it’s root node.
Note
Path Compression has the benefit of avoiding the creation of tall trees
Implementation
There are two ways this can be achieved:
Two Pass Implementation
After finding a node, add a second loop to find the root node and set the current node’s parent accordingly.
Path Halving
Make every node’s parent point to it’s grandparent instead. Very simple to implement and cheap.