Visualizer CodeViz · Algorithms, visualized

Part I · Union–Find · week 1

Path compression

Every find already walks to the root, so pay one more pass and point the whole path at it. The result is essentially constant time per operation.

Run the animation, step by step → generated live from any input you type — nothing is pre-recorded

Cost and properties

amortisedO(α(n)) — all but constant
m ops on n sitesc·(n + m lg* n)
optimal?no linear-time algorithm exists
space2n

Reference: Sedgewick & Wayne, §1.5; Tarjan 1975.

Path compression in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

class WeightedQuickUnionPathCompressionUF:
    def __init__(self, n):
        self.id = list(range(n))
        self.sz = [1] * n

    def find(self, p):
        root = p
        while root != self.id[root]:      # pass 1: locate the root
            root = self.id[root]
        while p != root:                  # pass 2: flatten the path
            nxt = self.id[p]
            self.id[p] = root
            p = nxt
        return root

    def union(self, p, q):
        i, j = self.find(p), self.find(q)
        if i == j:
            return
        if self.sz[i] < self.sz[j]:
            self.id[i] = j
            self.sz[j] += self.sz[i]
        else:
            self.id[j] = i
            self.sz[i] += self.sz[j]

Why it works

The idea

The first pass of find already visited every node on the path to the root. Those nodes will be searched again later, and they all belong to the same component — so point them straight at the root while the information is free. Each find makes the structure permanently flatter: the algorithm improves the data structure as it reads it.

Do not write the one-liner

The tempting p, self.id[p] = self.id[p], root is wrong in Python: targets are assigned left to right, so p is rebound before self.id[p] is stored and you compress the wrong node. Keep the explicit nxt temporary.

The cost claim

Weighted quick-union with path compression performs m operations on n sites in time proportional to n + m lg* n — and lg* n is at most 5 for any n you can store. It is not linear (Fredman–Saks proved no linear-time algorithm exists for this problem), but it is indistinguishable from linear in practice.

What to watch

Step through a find on a deep node: the second loop rewrites each pointer on the way. Do the same find again — it now takes one hop. The classic alternative, path halving (id[p] = id[id[p]], one pass), earns the same bound with less code.

What to try in the animation

n sites, then a list of p-q pairs to connect. The default is tinyUF.txt from the course.

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

Open Path compression in the player →

The rest of Union–Find