61Union-Find — are these two connected?

In Chapter 60 we built the graph — the structure that stores every relationship as an edge and lets us walk them. But one question we kept asking it, are these two things connected?, 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. Here's the plan. We'll meet a structure that stores no paths at all, only who is grouped with whom. 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. You'll explain why it runs in effectively constant time. And you'll recognise 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 in 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 interleaved with the merges, someone keeps asking: are these two particular things now in the same island? That's it. That's the entire job. The formal name for the groups is 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.

Where does this actually show up? Three places you have already used. When Photoshop's paint bucket floods a region, it is merging touching pixels into one blob and asking which blob a pixel belongs to. When a network tool checks whether two machines can still reach each other after cables are added one by one, that is merge-and-ask. And Kruskal's algorithm for the cheapest set of roads that connects every town adds a road only when it would join two separate groups — a "same group?" test on every single step. The surface stories look nothing alike. The shape underneath is identical: things merge, and you keep asking who ended up together.

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. Each time someone asks, run a BFS from A and 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, aimed up at the "representative" of its group. Follow those parents and you climb a tree. The element at the very top points at itself, and that self-pointer marks the root, whose own index is the group's label. Every element in a group climbs to that same root, so the question "same group?" becomes "same root?". A single group is one tree, and the whole collection is a forest of these upward-pointing trees.

Now the memory move. A tree usually means scattered heap nodes joined by real pointers. That's 28-byte object headers and cache-missing pointer-chasing, the whole tax we paid for the linked list and the graph. Union-Find pays none of it. 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. It's 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.

Why does one flat array beat a tree of heap nodes so badly? It comes down to how the CPU actually fetches memory. Hardware never pulls a single byte. It pulls a whole cache line, 64 bytes at once, into fast on-chip memory. In an array('i') of 4-byte ints, one line holds 16 consecutive elements, so reading parent[i] often drags parent[i+1] and its neighbours along for free. Heap nodes scatter across pages instead, and each pointer-hop risks a cache miss — a stall of a hundred-plus cycles while the CPU waits on RAM. The forest-in-an-array keeps the climb close and cache-warm, and that locality is half of why Union-Find feels instant.

Let's make that array concrete with six elements, 0 through 5. Say parent = [0, 0, 1, 1, 4, 4]. To find 2's root, read parent[2], which is 1. Then read parent[1], which is 0. Then parent[0] is 0 — a self-pointer — so 0 is the root. Element 3 climbs the same way and also lands on 0, so 2 and 3 share a group. But 5 reads parent[5] = 4, then parent[4] = 4, so 5's root is 4, a different group. The whole membership question came down to a few array reads and one comparison. No walking, no traversal, just following numbers up a ladder.

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). That 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, or 4.09 B each. There are no boxed int objects to reference now, 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.

import sys, random
from array import array
from collections import defaultdict, deque

random.seed(61)
V, E = 50_000, 100_000
edges = [(random.randrange(V), random.randrange(V)) for _ in range(E)]

def gbytes(d):                            # the dict, plus every list it owns
    return sys.getsizeof(d) + sum(sys.getsizeof(v) for v in d.values())

adj    = defaultdict(list)                # the graph way: keep every edge
parent = array('i', range(V))             # the union-find way: one int per element

def root(x):                              # the climb section 02 just taught
    while parent[x] != x: x = parent[x]
    return x

for n, (a, b) in enumerate(edges, 1):
    adj[a].append(b); adj[b].append(a)    # graph: 2 entries per edge, kept forever
    ra, rb = root(a), root(b)
    if ra != rb: parent[ra] = rb          # union-find: ONE write, edge never stored
    if n in (1, 10_000, 100_000):
        print(f"{n:>7,} edges in:  adjacency {gbytes(adj):>9,} B   parent {sys.getsizeof(parent):>8,} B")

def bfs(a, b):                            # the graph's answer, walked
    seen, q = {a}, deque([a])
    while q:
        x = q.popleft()
        if x == b: return True
        for y in adj[x]:
            if y not in seen: seen.add(y); q.append(y)
    return False

lonely = next(v for v in range(V) if v not in adj)
for a, b in [(0, 1), (123, 45_678), (0, lonely)]:
    print(f"  connected({a}, {b})?  BFS {bfs(a, b)}   root(a)==root(b) {root(a)==root(b)}")

      1 edges in:  adjacency       408 B   parent  209,420 B
 10,000 edges in:  adjacency 2,041,872 B   parent  209,420 B
100,000 edges in:  adjacency 7,604,424 B   parent  209,420 B
  connected(0, 1)?  BFS True   root(a)==root(b) True
  connected(123, 45678)?  BFS True   root(a)==root(b) True
  connected(0, 209)?  BFS False   root(a)==root(b) False

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 run the whole structure, and the flat array makes both of them 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. That element is the root, and you return it. union(a, b) merges two groups by finding a's root, finding b's root, and, if they differ, setting one root's parent to the other. That single write, parent[rootA] = rootB, staples two trees into one, and instantly every element under rootA climbs to rootB. "Connected?" is then just find(a) == find(b).

Trace one union on that same array. Right now the two trees have roots 0 and 4, sitting apart. Call union(3, 5). First find(3) returns root 0, and find(5) returns root 4. The roots differ, so we staple one under the other with a single write: parent[4] = 0. Now the array is [0, 0, 1, 1, 0, 4], and everything — 2, 3, 4, and 5 — climbs to 0. One assignment merged two whole groups at once. Ask connected(2, 5) a moment later and both climb to root 0, so the answer is now yes where seconds ago it was no. That is the entire data structure working.

One more question falls out for free: how many separate groups are left? Just count the roots, the indices where parent[i] == i. Back on parent = [0, 0, 1, 1, 4, 4], only 0 and 4 point at themselves, so there are exactly two groups. Better still, you can track the count without ever scanning. Start it at n, since every element begins as its own group, and drop it by one on each union that actually merges. Here is why that must hold: a successful union turns one root into a child, erasing exactly one self-pointer. So merging 6 singletons down to a single group takes precisely 5 unions, the same 5 edges any tree on 6 nodes needs. Connected-component counting, a whole classic problem, is just this counter read off at the end.

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 is a fully working Union-Find already. find is a loop that follows parents until it hits the self-pointer. union calls it twice and does one assignment when the roots differ, and connected is a one-liner on top. It is correct, but read find again with a suspicious eye. Its cost is the height of the tree — the number of parent-hops from x up to the root — and nothing here controls that height. If unions keep stapling roots into a straight line, say 0 under 1 under 2 under 3, the tree becomes a chain of length n. Then find degrades to O(n), a linked list wearing a forest's clothes.

When does that dreaded chain actually form? You do not need an adversary — a natural order is enough. Watch naive union merge lone elements in sequence. union(0, 1) points 0 at 1. union(1, 2) finds 1's root and points it at 2, dragging 0 along beneath. Do union(2, 3), then union(3, 4), and each step hangs the growing tree under the fresh lone element. After n such merges you have one long chain, 0 at the bottom and the newest element on top. A find on the bottom now pays the full O(n) climb. Nothing tricky happened. Merging in the most obvious order was all it took to build the worst case, and that is exactly the leak the next two sections plug.

Play with it yourself. Click any two circles below to union their groups, and watch the parent-arrows rewire as the parent array updates live. Click two that already sit in the same tree and it tells you they were already connected. That is connected() answering the question without doing a single merge.