Path Compression

The Idea

Unions can build a long chain, and then every find re-walks it. But the walk already learned the answer.

So make a second pass over the same path and point each node straight at the root. The path you paid for once is flat for everyone who uses it afterwards.

Real-World Example

A phone menu that forwards you through three departments before reaching the one person who can help. The second time you call their direct number. Nobody re-derives the route because the route was worth writing down.

The Code

parent = [1, 2, 3, 4, 4]        # a 0 -> 1 -> 2 -> 3 -> 4 chain
def find(x):
    root = x
    while parent[root] != root:  # first pass: locate the root
        root = parent[root]
    while parent[x] != root:     # second pass: re-point the whole path
        parent[x], x = root, parent[x]
    return root

print(find(0), parent)

parent = [1, 2, 2]
def find(x):
  root = x
  while parent[root] != root:
      root = parent[root]
  while parent[x] != root:
      parent[x], x = root, parent[x]
  return root
find(0)
print(parent)