Path compression is a Union-Find optimization that shortens parent chains during find.
It makes future find operations faster by pointing visited nodes closer to the root.
Core Idea
When find(x) discovers the representative of x, every node on the path can be updated to point directly to that representative.
This does not change which set any element belongs to. It only improves the internal structure.
Python Example
class UnionFind:
def __init__(self, size):
self.parent = list(range(size))
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]The assignment inside find compresses the path.
Common Confusions
Path compression happens during find, not only during union.
It may make the parent array look different from a simple tree diagram, but the represented groups stay the same.
When To Use It
Use path compression in practical Union-Find implementations unless there is a special reason to keep the parent structure unchanged.