61Union-Find — are these two connected?

In Chapter 60 we built the graph — the structure that stores every relationship as an edge so we can walk them. But one question we kept putting to it, are these two things connected?, really deserves its own specialist. A graph answers it by re-walking the whole blob every single time, then throwing the answer away when it's done. So here's the plan. We'll meet a structure that stores no paths at all — only who is grouped with whom — and it answers two questions faster than anything else can: are A and B in the same group? and merge A's group into B's. The whole way through, we keep asking the one thing that matters: how do you remember that two things are connected without remembering how? By the end you'll build the entire thing in a dozen lines, explain why it runs in effectively constant time, and start spotting the surprising number of famous problems that are secretly just "merge groups and ask whether two things landed in the same one."

01One question, asked a billion times

Let's start with the one question this whole chapter is built to answer fast. Picture a set of things — pixels, computers, people, cities — that start out as n separate islands, each a group of one. Now relationships arrive one at a time: this pixel matches that pixel, this wire connects those two machines, these two people are friends. Each relationship merges two islands into one. And in between the merges, someone keeps asking: are these two particular things now in the same island? That's it — that's the entire job. The groups have a formal name, disjoint sets: a family of sets with no overlap, where every element belongs to exactly one. The structure that maintains them is the disjoint-set union, or Union-Find after its two operations.

Watch what the obvious approach costs. You could answer "connected?" with a graph traversal — the very tool we built last chapter. Store every relationship as an edge, and each time someone asks, run a BFS from A to see if you reach B. But that's O(V+E) per question. You re-walk the whole component every single time, then throw the answer away when you're done. Union-Find makes a different deal with memory. It doesn't remember how A and B are connected — no path, no route — only that they're in the same group, boiled down to one number. Forget the route, keep the label, and the question that cost a full traversal collapses to comparing two integers.

So each group needs a single label every member agrees on. Where does that label come from, and how does it live in memory? The answer is the cleverest small idea in this volume: a whole forest of trees, folded flat into one integer array. →

02The parent array — a forest hiding in a flat array

Here's the trick that makes the label cheap: don't store a label at all — store a parent. Give every element one pointer, up toward the "representative" of its group. Follow those parents and you climb a tree; the element at the very top — the one that points at itself — is the root, and the root's own index is the group's label. Every element in a group climbs to the same root, so "same group?" becomes "same root?". A group is a tree; the whole collection of groups is a forest of these upward-pointing trees.

Now the memory move. A tree usually means scattered heap nodes joined by real pointers — 28-byte object headers, cache-missing pointer-chasing, the whole tax we paid for the linked list and the graph. Union-Find pays none of it, because the elements are the integers 0..n-1, and an integer can be an index. So the entire forest collapses into one flat array, parent, where parent[i] holds the index of i's parent. No nodes, no heap pointers — the "pointer up the tree" is just a number you use to index back into the same array. A tree living inside a contiguous block, exactly the way the heap chapter folded a tree into an array. The root is any i where parent[i] == i.

import sys
from array import array

n = 1_000_000
parent = list(range(n))          # start: everyone is their own root (n islands)
sys.getsizeof(parent)            # -> 8,000,056   bytes  (8.00 B per element)

parent = array('i', range(n))    # same forest, packed 4-byte ints
sys.getsizeof(parent)            # -> 4,091,948   bytes  (4.09 B per element)

Line by line: the initial state is list(range(n)) — every element is its own parent, so every element is a root and the forest is n single-node trees. As a plain list it's a contiguous array of 8-byte references (Vol 1) — measured 8,000,056 bytes for a million elements, a flat 8.00 B per element. Swap in array('i') and the same information packs into raw 4-byte integers — 4,091,948 bytes, 4.09 B each — because there are no boxed int objects to reference, just the numbers themselves. Either way the cost is O(n), one slot per element, and that's the whole structure: no per-edge storage, no node headers. Union-Find is one of the lightest containers you'll ever meet.

One array, one rule ("roots point at themselves"). From those, both operations fall out almost for free — and one of them has a hidden performance trap that a person had to be clever to escape. →

03find and union — follow the parents, repoint a root

Two operations, and the array makes both obvious. find(x) answers "which group?" by climbing: start at x, hop to parent[x], then parent[parent[x]], and keep going until you reach the element that points at itself — the root. Return that root. union(a, b) merges two groups: find a's root, find b's root, and if they differ, set one root's parent to the other. That single write — parent[rootA] = rootB — staples two trees into one, and instantly every element under rootA now climbs to rootB. "Connected?" is just find(a) == find(b).

def find(parent, x):
    while parent[x] != x:        # climb until a self-pointer (the root)
        x = parent[x]
    return x

def union(parent, a, b):
    ra, rb = find(parent, a), find(parent, b)
    if ra != rb:                 # different groups?
        parent[ra] = rb          # one write staples them together

def connected(parent, a, b):
    return find(parent, a) == find(parent, b)

That's a fully working Union-Find. find is a loop that follows parents until the self-pointer; union calls it twice and, if the roots differ, does one assignment; connected is a one-liner on top. It's correct — but read find again with a suspicious eye. Its cost is the height of the tree: how many parent-hops from x up to the root. Nothing here controls that height. If unions keep stapling roots into a straight line — 0 under 1 under 2 under 3 — the tree becomes a chain of length n, and find degrades to O(n), a linked list wearing a forest's clothes.

Play with it. Click any two circles below to union their groups; the parent-arrows rewire and the parent array updates live. Click two that are already in the same tree and it tells you they were already connected — that's connected() answering without a single merge.