Visualizer CodeViz · Algorithms, visualized

Part I · Union–Find · week 1

Quick-find

Keep a component identifier for every site. Find is instant; union has to relabel a whole component, and that is what makes it too slow for large inputs.

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

Cost and properties

unionO(n)
findO(1)
spaceO(n)
n unionsquadratic — unusable at scale

Reference: Sedgewick & Wayne, §1.5.

Quick-find 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 QuickFindUF:
    # id[i] is the component identifier of site i. Two sites are connected
    # exactly when their ids are equal, so find is a single array read.

    def __init__(self, n):
        self.id = list(range(n))          # every site starts alone

    def find(self, p):
        return self.id[p]                 # the identifier IS the answer

    def connected(self, p, q):
        return self.find(p) == self.find(q)

    def union(self, p, q):
        pid, qid = self.id[p], self.id[q]
        if pid == qid:
            return                        # already in one component
        for i in range(len(self.id)):     # relabel ALL of p's component
            if self.id[i] == pid:
                self.id[i] = qid

Why it works

The data structure

An array id[] of component identifiers. The invariant is blunt: two sites are connected if and only if id[p] == id[q]. Nothing else is stored, so find cannot be beaten — one array access.

Why it is too slow

union must make the invariant true again, and the only way is to visit every entry. Connecting n sites therefore costs on the order of n2 array accesses. Watch the accesses counter: on 10 sites it is already in the hundreds. At n = 109 — the size the percolation and network problems actually reach — that is 1018 accesses, or 30 years of computing.

This is the course's first lesson about quadratic algorithms do not scale, and it does not go away with a faster machine: a 10× faster computer buys you a 3× larger problem.

What to watch for

  • The relabel loop touches sites that are not in either component — it reads all n entries to find the few it must change.
  • The target id is qid, the identifier of q's component, so the picture is always one level deep: every site points straight at its identifier.
  • Try the worst case: a path preset. Each union relabels an ever larger component.

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 Quick-find in the player →

The rest of Union–Find