Path Compression

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.

Class Contract

The example UnionFind stores a parent array where each element eventually points to a root representative.

find(x) returns that representative and rewrites parent pointers along the way. The represented groups do not change; only the internal path length changes.

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.

Step-by-Step Idea

Suppose the parent chain is:

5 -> 3 -> 1 -> 1

The root is 1. After find(5) with path compression, the structure can become:

5 -> 1
3 -> 1
1 -> 1

Future calls to find(5) or find(3) are shorter.

Why It Is Safe

Path compression does not merge or split groups. Every node on the path already belonged to the same group because all of them eventually reached the same root. Pointing them directly to that root preserves the group identity.

Complexity Effect

Path compression is most powerful when combined with union by size or rank. Together they make Union-Find operations amortized near constant time for practical use.

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.

Another common mistake is trying to compress paths without returning the root correctly. The recursive function must still return the representative.

When To Use It

Use path compression in practical Union-Find implementations unless there is a special reason to keep the parent structure unchanged.

If the problem only has a tiny number of operations, the optimization may not matter, but it is still the standard implementation habit.

The Main Point

Path compression makes future find calls faster without changing any group membership.