◈ python mapVol 4 · Ch 61/62
Volume 4 Python, from the metal up · chapter 61

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."

★ YOU ALREADY RUN THIS · the-two-tablesone introduction, and two circles of strangers become one — permanently
Table four, somewhere between the speeches and the cake. Eight of you, sat as two clumps: your lot down one end, the couple's cousins down the other, nobody crossing. Then Aisha turns round, says oh — you two should know each other, and puts Marco in front of you. Nobody re-introduces everybody to everybody. One handshake, and it is one table. An hour later somebody asks how you know the bride and you do not say through Aisha, who knows Priya, who… — you say “I'm with Priya's lot”, because that is the only thing that survived the evening. The route is gone. The label is all anyone kept.
one introduction, and the two clumps are one table→union(a, b) — find each circle's central figure, point one at the other. ONE write merges everybody, not everybody-to-everybody
“how do you two know each other?” and you both answer Priya→find(x) climbs the parent chain to the root. Same root = same circle, so the whole question is one comparison, never a search
after one party you stop retelling the chain and just say “Priya's lot”→path compression — the climb you had to do anyway re-points everyone you passed straight at the root. Free, and it stays flat
the small clump joins the big one, never the other way round→union by size: hang the smaller tree under the bigger root and the climb can never grow past log n. One if on a size dict is the whole fix
you could not reconstruct who introduced whom if you tried→the route was never stored. Union-Find keeps the label and throws the path away — that amnesia is the speed
pin it: a circle does not remember how it formed — only who it answers to. Forget the route, keep the label, and “are these two connected?” stops being a search.
iolinked · chapter 61 — the checkpoints6 steps
$ sections covered in Union-Find — are these two connected? —
›01One question, asked a billion times
›02The parent array — a forest hiding in a flat array
›03find and union — follow the parents, repoint a root
›04Path compression — flatten the trail on the way up
›05Union by size — never hang the big tree off the small one
›06α(n) — the cost that never reaches 5

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.

graph way: BFS re-walks the blob (O(V+E) each ask) A · · · B visit node, scan neighbours, repeat… every time Union-Find way: each group wears one label group label = 2 A · B label(A) == label(B)? → one comparison
Fig — the whole idea. A traversal answers "connected?" by re-exploring the blob. Union-Find pre-collapses each blob to a single label, so the same question becomes "do these two carry the same label?" — a comparison, not a walk.

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.

the forest (a drawing) 2 0 1 3 root (label 2) 5 4 6 root (label 5) 7 alone: 7→7 …is really just this one contiguous array in RAM 0123 4567 2 2 2 0 5 5 5 7 parent[2]=2 → root parent[5]=5 → root parent[7]=7 → root
Fig — the memory layout. Three groups, drawn as upward trees, are one 8-cell array: parent[i] is i's parent index. Roots point at themselves (highlighted). No heap nodes, no real pointers — the whole forest is a flat run of integers you index into.
up.pypython
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.

A forest, not a tree — and the root names the group
There are as many trees as there are groups, and they share one array. The only thing that makes an element "special" is parent[i] == i: that self-loop marks a root, and the root's index is the group's identity. Merging two groups will be nothing more than making one root point at the other — one array write.

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.

ops.pypython
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.

Naive union can build a comb — and then find is O(n)
Because union blindly does parent[ra] = rb, an adversarial (or just unlucky) order of merges can grow one long spindly chain. Every find then walks the whole chain. On a real run of a 200,000-element chain, one find of the deepest node measured about 3.8 ms — millions of times slower than it needs to be. The layout is perfect; the shape is the enemy.

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.

InteractiveClick two elements to union — watch the forest merge
Click an element…
groups: 8
Same root = same group. union() staples two roots together; connected() just compares the two roots.
↺ The thing people get backwards
Union-Find feels like a graph, so people expect it to tell them how two elements connect — the path between them, or the list of everyone in a group. It won't, cheaply. The parent pointer aims at a representative, not at the neighbour you merged with; the tree's shape is an accident of merge order, not the real relationships. Union-Find deliberately forgets the route and keeps only the label. That amnesia is the whole point — it's why the answer is one comparison instead of a traversal. Need the actual paths or members? You want the graph of d12, not this.

A person stared at that O(n) chain and asked: on the way up to the root, I touch every node on the path anyway — why not fix them while I'm here? That one thought is worth a 19,000× speedup. →

04Path compression — flatten the trail on the way up

Here's the first great optimization, and it's almost embarrassingly cheap. When find(x) climbs to the root, it walks past every node on the path from x upward. Those nodes now know who the root is. So on the way back, re-point every one of them straight at the root. The next time you call find on any of them, it's one hop. You did the walk anyway; flattening the path is free work that permanently shortens the tree. This is path compression, and it turns a tall spindly tree into a flat bush after a single query.

Make it concrete on a five-node chain: parent = [0, 0, 1, 2, 3], so 4 sits under 3 under 2 under 1 under root 0. Call find(4). It climbs 4 → 3 → 2 → 1 → 0, four hops to reach the root. Compression then rewrites every node it passed to point straight at 0, leaving parent = [0, 0, 0, 0, 0]. Now 2, 3, and 4 are each one hop from the root. The next find(4) costs a single read instead of four, and you paid nothing extra for it — you were already walking that path on the way up. That is the trick in one image: the climb you had to do anyway leaves the tree permanently flatter behind you.

compress.pypython
def find(parent, x):
    root = x
    while parent[root] != root:      # pass 1: climb to the root
        root = parent[root]
    while parent[x] != root:         # pass 2: bend every node on the path to root
        parent[x], x = root, parent[x]
    return root

Pass one finds the root as before. Pass two walks the same path a second time and rewrites each node's parent to be the root directly. The tuple assignment saves the old parent before overwriting it, so the walk can continue. Two cheap passes instead of one, and the tree collapses. Here's the payoff, measured on that same 200,000-node chain. The first compressed find still pays O(n) to climb, about 10 ms, one time. But it flattens everything, so every subsequent find of that node drops to about 0.20 µs, versus 3,793 µs naive. That's roughly a 19,000× speedup per query, and it came from noticing you were already standing on those nodes.

Write find as a loop, not recursion
The tempting one-liner return x if parent[x]==x else find(parent, parent[x]) is elegant and crashes in production. Before compression kicks in, a tree can be tens of thousands deep, and Python's default recursion limit is just 1000 — a recursive find on a depth-4999 chain raises RecursionError (verified). The iterative two-pass version above has no such ceiling. This is a real bug that ships: the structure is provably shallow eventually, but the very first deep find — the one that would have flattened it — is exactly the call that blows the stack.

Watch it happen for yourself. Below is a deliberately tall chain, with 5 hanging under 4 under 3 and so on down to root 0. Press find(5) and the path folds flat as every node on it re-points directly at 0. The hop-count for a future find(5) drops from 5 all the way to 1.

Interactivefind(5) — watch the path compress to the root
A chain of depth 5. find(5) must climb 5 hops.
hops: 5
You walk the path to answer the query anyway — so bend every node straight to the root while you're there. Free.

Compression fixes trees after they grow tall. But there's a second, complementary idea that stops them growing tall in the first place — and it's just as simple. →

05Union by size — never hang the big tree off the small one

The second optimization attacks the problem at union time. When you merge two trees, you choose which root becomes the child of the other, and that choice decides the new height. Attach the bigger tree's root on top and hang the smaller under it, and the combined tree stays as short as possible. Do it backwards and you risk stacking height on height. Keep a size array, how many elements each root owns, and always point the smaller root at the larger. This is union by size. Its cousin, union by rank, tracks tree height instead, in the same spirit. Alone, it guarantees no tree is ever taller than O(log n). A tree can only get taller when two equal-size trees merge, and that can happen at most log₂n times on the way from 1 to n.

Here is why that height cap is airtight, not hand-waving. Under union by size, a tree only grows taller when it hangs beneath a root at least as big as itself, so its height can rise only when its element count at least doubles. Count it out: a tree of height 1 needs at least 2 elements, height 2 needs at least 4, height 3 needs at least 8. Every extra level at least doubles the population underneath it. So a tree holding n elements can be at most log₂n tall. With a million elements that is a height of about 20, not a million. The O(n) comb becomes structurally impossible the moment the size array gets a vote.

✗ small root on top → tall r height grows every merge → O(n) ✓ big root on top → flat R height ≤ log₂n, always
Fig — the union you choose decides the height. Hang the small tree under the big root (right) and depth stays logarithmic; do it backwards (left) and you can build the O(n) comb. One if on the size array is the whole fix.
r_b.pypython
def union(parent, size, a, b):
    ra, rb = find(parent, a), find(parent, b)
    if ra == rb:
        return
    if size[ra] < size[rb]:          # ensure ra is the LARGER root
        ra, rb = rb, ra
    parent[rb] = ra                  # small tree hangs under big root
    size[ra] += size[rb]             # big root absorbs the count

The extra machinery is one comparison and one addition. If ra's tree is smaller, swap the labels so ra is always the bigger root. Then hang rb under ra and fold the sizes together. The cost is one more n-length array, the size counts. That doubles the structure's footprint to about 8 B/element as two packed int arrays, still gloriously light. And now, crucially, height never exceeds log n on its own.

Watch it defeat the exact sequence that beat us before. Those same merges — union(0,1), union(1,2), union(2,3), union(3,4) — built a height-4 chain under naive union. Now run them with size in charge. The first merge makes a tree of size 2 rooted at 0. Every later element arrives as a lone singleton of size 1, so it loses the tie and hangs directly under root 0. The array ends as [0, 0, 0, 0, 0]: a flat star, not a chain. A find that paid 4 hops before now pays exactly 1. The worst input from two sections ago just collapsed into the best case, and all it took was one look at the size array.

THE STDLIB TOOLBELT · the honest card — there is no import unionfindfifteen lines you will re-type for the rest of your life — find, union by size, and the cycle it catches
# there is no union-find in the stdlib. these fifteen lines ARE the tool. parent, size = {}, {} # element -> its parent, root -> its headcount def find(x): root = x while parent[root] != root: # pass 1: climb to the root root = parent[root] while parent[x] != root: # pass 2: bend the whole trail flat parent[x], x = root, parent[x] return root def union(a, b): ra, rb = find(a), find(b) if ra == rb: return False # already together - this edge closes a CYCLE if size[ra] < size[rb]: ra, rb = rb, ra # make ra the BIGGER circle parent[rb] = ra # the small table joins the big one size[ra] += size[rb] return True connected = lambda a, b: find(a) == find(b) # the entire query
parent, size = {}, {}A dict, not the chapter's flat array — because real elements are names, pixels, and account ids, not the integers 0..n−1. You trade the array's cache-warm climb for the freedom to union anything hashable. Same algorithm, same α(n); a fatter constant.
parent[x], x = root, parent[x]The whole of pass two. The right-hand side is built before either name is rebound, so the old parent is safely in hand as the new one is written — the walk survives its own rewrite. Write it as two statements in the wrong order and the loop eats itself.
if ra == rb: return FalseNot an early exit — a discovery. The two were already connected, so this edge closes a cycle. Returning that boolean is exactly Kruskal's reject test (Vol 3), and it is how you count the merges that actually merged.
size[ra] < size[rb] → swapUnion by size. Its cousin, union by rank, is the same line over a rank dict that only ever increments on a tie: if rank[ra] == rank[rb]: rank[ra] += 1. Size is easier to reason about and hands you the component's headcount for free.
itertools.count() for labelsRoots are indices, not names. To hand each component a stable 0,1,2… label at the end: ids = defaultdict(count().__next__), then ids[find(x)] per element. Do it after the last union — see the third tripwire.
INPUTparent, size = {}, {}

def add(x):
    parent.setdefault(x, x)                  # a newcomer is their own circle
    size.setdefault(x, 1)

def find_plain(x):                           # NO compression - the naive climb
    while parent[x] != x:
        x = parent[x]
    return x

def find(x):                                 # WITH path compression
    root = x
    while parent[root] != root:              # pass 1: climb to the root
        root = parent[root]
    while parent[x] != root:                 # pass 2: bend the trail to the root
        parent[x], x = root, parent[x]
    return root

def union(a, b, f=find_plain):               # union BY SIZE
    add(a); add(b)
    ra, rb = f(a), f(b)
    if ra == rb:
        return False                         # already the same circle
    if size[ra] < size[rb]:
        ra, rb = rb, ra                      # ra is the BIGGER circle
    parent[rb] = ra                          # the smaller table joins the bigger
    size[ra] += size[rb]
    return True

table_A = [("Nikhil", "Priya"), ("Aisha", "Dan"), ("Priya", "Aisha")]
table_B = [("Lena", "Marco"), ("Jo", "Ben"), ("Marco", "Jo")]
for a, b in table_A + table_B:
    union(a, b)

print("two tables, nobody has crossed the room yet")
print("  parent:", parent)
print("  sizes :", {k: v for k, v in size.items() if parent[k] == k})
print("  Dan and Nikhil same circle?", find_plain("Dan") == find_plain("Nikhil"))
print("  Dan and Ben    same circle?", find_plain("Dan") == find_plain("Ben"))
print("  circles left:", sum(1 for k in parent if parent[k] == k))

print("\nAisha turns round and introduces Marco. ONE union.")
merged = union("Aisha", "Marco")
print("  merged something new?", merged)
print("  parent:", parent)
print("  Dan and Ben    same circle?", find_plain("Dan") == find_plain("Ben"))
print("  circles left:", sum(1 for k in parent if parent[k] == k))

def climb(x):
    trail = [x]
    while parent[x] != x:
        x = parent[x]; trail.append(x)
    n = len(trail) - 1
    return " -> ".join(trail) + f"  ({n} hop{'s' if n != 1 else ''})"

for who in ("Dan", "Ben", "Jo"):
    print(f"  {who:6} climbs:", climb(who))

print("\nask Ben ONCE, with compression - the climb pays itself forward")
print("  find('Ben') ->", find("Ben"))
print("  parent:", parent)
for who in ("Dan", "Ben", "Jo"):
    print(f"  {who:6} climbs:", climb(who))
print("  same answers? Ben~Dan:", find("Ben") == find("Dan"),
      " Ben~Nikhil:", find("Ben") == find("Nikhil"))
OUTPUTtwo tables, nobody has crossed the room yet
  parent: {'Nikhil': 'Nikhil', 'Priya': 'Nikhil', 'Aisha': 'Nikhil', 'Dan': 'Aisha', 'Lena': 'Lena', 'Marco': 'Lena', 'Jo': 'Lena', 'Ben': 'Jo'}
  sizes : {'Nikhil': 4, 'Lena': 4}
  Dan and Nikhil same circle? True
  Dan and Ben    same circle? False
  circles left: 2

Aisha turns round and introduces Marco. ONE union.
  merged something new? True
  parent: {'Nikhil': 'Nikhil', 'Priya': 'Nikhil', 'Aisha': 'Nikhil', 'Dan': 'Aisha', 'Lena': 'Nikhil', 'Marco': 'Lena', 'Jo': 'Lena', 'Ben': 'Jo'}
  Dan and Ben    same circle? True
  circles left: 1
  Dan    climbs: Dan -> Aisha -> Nikhil  (2 hops)
  Ben    climbs: Ben -> Jo -> Lena -> Nikhil  (3 hops)
  Jo     climbs: Jo -> Lena -> Nikhil  (2 hops)

ask Ben ONCE, with compression - the climb pays itself forward
  find('Ben') -> Nikhil
  parent: {'Nikhil': 'Nikhil', 'Priya': 'Nikhil', 'Aisha': 'Nikhil', 'Dan': 'Aisha', 'Lena': 'Nikhil', 'Marco': 'Lena', 'Jo': 'Nikhil', 'Ben': 'Nikhil'}
  Dan    climbs: Dan -> Aisha -> Nikhil  (2 hops)
  Ben    climbs: Ben -> Nikhil  (1 hop)
  Jo     climbs: Jo -> Nikhil  (1 hop)
  same answers? Ben~Dan: True  Ben~Nikhil: True
TRIPWIRES
The deeper cut — why the two tricks together beat either alone

Union by size alone gives O(log n) per operation, and path compression alone also gives roughly O(log n) amortized, but neither one is constant on its own. The magic is that the two compound. With both switched on, a sequence of m operations on n elements costs O(m · α(n)) total, where α is the inverse Ackermann function from the next section. That total is indistinguishable from linear. The intuition is short. Union-by-size keeps every tree short, so a climb is already cheap, and every climb that does happen pays it forward by flattening the path it walked. That leaves the tree structurally harder to make deep again. Tarjan's 1975 analysis proved this bound is not merely an average but genuinely tight.

Line the three regimes up on a concrete n = 1,000,000 and the whole arc snaps into focus. With no help at all, a find on the pathological chain climbs the full 1,000,000 hops. Add union by size alone and the tree can be at most log₂(1,000,000) tall. That is about 20 hops, since 2²⁰ ≈ 1.05 million. Switch on path compression too and the measured climb drops to roughly 1.11 hops. A million, then twenty, then basically one: that is the same operation, three times, as each trick does its share of the work.

There's also a slicker one-pass compression called path halving. As you climb, set each node's parent to its grandparent (parent[x] = parent[parent[x]]; x = parent[x]). It halves the path in a single loop and needs no second pass. It achieves the same α(n) bound, and it's the version most production libraries ship.

Union by size caps height at log n; compression crushes it further toward 1. Put them together and the per-operation cost sinks to a number so small it has a famous, almost unbelievable name. →

06α(n) — the cost that never reaches 5

Wait —
if the cost still technically grows with n, how can anyone call it constant? Because the thing it grows as is so slow that "grows" loses its teeth. Meet the slowest-rising function that ever earned a Big-O.

With both optimizations, a Union-Find operation runs in O(α(n)) amortized time, where α is the inverse Ackermann function. The Ackermann function A(m,n) is the standard example of something that grows faster than any tower of exponentials. It explodes so violently that its inverse crawls upward almost imperceptibly. How slowly? α(n) stays ≤ 4 for every n up to a number with roughly 19,729 digits. The observable universe has about 10⁸⁰ atoms, an 81-digit number. So for any Union-Find you will ever build — indeed for any that could physically exist — α(n) is a small constant no bigger than 4. It is not literally O(1), but the gap is philosophical, not practical.

Ackermann explodes → its inverse α(n) barely moves A(m,n) — grows past all towers A(2,4) = 11 A(3,4) = 125 A(4,1) = 65,533 A(4,2) = 2⁶⁵⁵³⁶ − 3 (19,729 digits long) universe ≈ 10⁸⁰ (81 digits) α(n) — the inverse, per operation n ≤ 3 ....... α = 1 n ≤ 7 ....... α = 2 n ≤ 2047 .... α = 3 n ≤ (19729 digits) .. α = 4 → effectively constant, forever
Fig — why "almost O(1)" is honest. Ackermann outruns every exponential (A(4,2) already has 19,729 digits); its inverse α therefore stalls at 4 across every input the physical universe permits. Verified in Python: A(4,1)=65,533, and 2⁶⁵⁵³⁶ prints 19,729 digits.

The real proof is in a stopwatch, not a formula. Here is a full Union-Find with both tricks, run on a million elements and counting the real parent-hops per operation:

alpha.pypython
# n = 1,000,000 elements, 1,000,000 random unions, both optimizations on
avg_parent_hops_per_find  = 1.11     # after all unions, averaged over n finds
amortized_hops_per_union  = 1.34     # total climbs / total unions across the run

# the same worst-case chain of 200,000 nodes:
naive_find_deepest        = 3793.0   # microseconds, O(n)
compressed_find_after     = 0.20     # microseconds, effectively O(1)
speedup_per_find          = 18965    # times faster

These are measured, not quoted. After a million random unions on a million elements, an average find climbs just 1.11 parent-hops to reach its root. That number barely budged — it was 1.11 at n=100,000 too — which is exactly what "independent of n" looks like in the wild. The amortized cost across a whole run is about 1.34 hops per union. And on the pathological chain, compression turns a 3,793 µs climb into a 0.20 µs one, the ~19,000× we promised. Timings are machine-dependent, so yours will differ in absolute terms. The ratio and the flatness are the structural facts.

Sit with that 1.11 for a second, because it is the whole point wearing a number. It means a real find, after all the compression and size-balancing, almost always reaches the root in one or two hops. The tree is essentially flat. Double the elements to two million and the figure stays near 1.11. Grow them ten-fold and it barely twitches. That flatness — not any single microsecond timing — is the promise of Union-Find: the work per question stops caring how big the problem got. A billionth query costs about what the first one did. Very few data structures can say that, and it is why this one shows up under so many famous algorithms.

That same flatness powers a trick worth its own name: cycle detection. When you call union(a, b) and find(a) already equals find(b), the two were already connected, so the new edge closes a loop. Take a triangle: edges (0,1), (1,2), (2,0) on three nodes. The first two merge 0, 1, and 2 into one group. The third edge, (2,0), finds them already sharing a root, so it is flagged as a cycle and skipped. That is precisely the reject test inside Kruskal's algorithm from the opening, keeping its growing road network a tree. And it runs in the same near-constant time as every other query.

InteractiveDrag n toward every atom in the universe — watch α(n) refuse to grow
PER-FIND COST · A NAIVE CHAIN vs BOTH TRICKS 10⁸⁰ pointer-hops · naive find → 4 pointer-hops · both tricks n = 10⁸⁰ — every atom in the observable universe naive · O(n) 10⁸⁰ union by size · O(log n) 266 both tricks · O(α(n)) 4 1 10²⁰ 10⁴⁰ 10⁶⁰ 10⁸⁰ ← number of pointer-hops per find (log scale) → Drag n up: the red bar rockets to 10⁸⁰ hops — the green bar ticks to 4 and stops. α reaches 4 and then never reaches 5 — not for any n with fewer than ~19,729 digits.
n = 10⁸⁰
Every set you could ever store fits on this chart. A naive find on a degenerate chain costs the count itself — up to 10⁸⁰ pointer-chases on a universe-sized set. Union-by-size alone caps a find at log₂n (≈266 even at 10⁸⁰). Add path compression and the amortized cost is α(n), the inverse Ackermann function: on this scale it ticks 3 → 4 (and is just 1 or 2 for a handful of tiny sets), then never reaches 5. That flat green bar is what "effectively constant" means — the rare cost that stops growing before the universe runs out of atoms.
Why the metal loves this structure
Two n-integer arrays, contiguous. A find after compression touches a handful of adjacent-ish cells that mostly sit in cache — the win Volume 3 taught us to chase — no 28-byte object headers, no heap pointer-chasing, no cache-missing node hops like the linked list or the dict-of-lists graph. The forest is logically a tree but physically a flat array, so the CPU streams it. Light in space and friendly to cache — the rare structure that wins on both axes.

Myth

There's an honest baseline worth stating first. To keep checking whether two things are connected as relationships pour in, you could just store a graph and BFS on each question, and it's simple and correct.

Reality

But that costs O(V+E) on every question, and it can never reuse the work it did between merges. Union-Find instead answers both "connected?" and "merge!" in effectively O(1) each, amortized. It becomes the right tool the moment the workload is incremental grouping with connectivity queries. It is not a graph replacement so much as the specialist built for that one access pattern.

One honest limit, so you reach for it correctly. Union-Find merges groups and never splits them. There is no cheap un-union, because a group is just "everyone who climbs to this root," and once paths are compressed the old shape is gone for good. It also will not list a group's members or hand you the route between two elements. It threw those away on purpose, and that discarding is exactly why it's fast. So if your problem needs deletions, membership lists, or actual paths, you want the graph, not this. Knowing what a structure refuses to do is half of knowing when to use it.

Where you meet this — more places than you'd guess
Kruskal's algorithm for the Minimum Spanning Tree (Vol 3, greedy) sorts edges and uses Union-Find to skip any edge whose endpoints are already connected — that's how it avoids cycles. Image segmentation merges neighbouring pixels of similar colour into regions (the classic Felzenszwalb algorithm is Union-Find under the hood). Percolation physics, maze generation (merge cells until the grid is one connected maze), "friend circles" / connected components in social graphs, network reliability ("is the grid still one piece after this cable fails?"), and type unification in compilers (merge two type variables that must be equal) are all this structure. You've almost certainly used a photo tool or a map router whose internals ran a find.

And here's the 1% move, the transferable one. "Good at data structures" is mostly matching a structure to an access pattern on sight. When you see a problem that's incremental merging plus "same group?" queries — and only that, no paths, no members, no deletions — the reflex should fire: this is Union-Find. Recognising it saves you from reaching for a heavyweight graph and re-traversing forever. The skill isn't memorising α(n). It's feeling the shape of "merge and ask" and knowing there's a near-free tool built for exactly it.

NOW COUNT THE CIRCLESa class, ten guests, and the number that falls out for free
The drill. Wrap the two functions into a UnionFind class, then answer the classic: given a list of “these two know each other” pairs, how many separate circles are in the room? Your class needs find with path compression, union by size, connected, and a live groups counter.

The counter is the trick, and it costs nothing. Start it at the number of guests, because everyone begins as a circle of one. Then drop it by exactly one on every union that actually merges — a successful union turns one root into a child, erasing exactly one self-pointer. Have union return True when it merged and False when the two were already together, so the redundant pairs announce themselves. Never scan the dict to count roots; you already know the answer.

The check. Feed it two four-person circles closed into rings (so the last pair in each ring is redundant), one pair off to the side, and a duplicate. Ten guests, ten pairs, but only seven of those pairs should report merged — the other three closed a cycle, which is Kruskal's reject test firing. You should land on 3 circles. Then run the one introduction that crosses the room and watch it become 2, in a single write.
show the solution
class UnionFind:
    """Groups that merge and never split. Two dicts, ~15 lines, no import."""

    def __init__(self, items=()):
        self.parent = {x: x for x in items}       # a newcomer is their own circle
        self.size = {x: 1 for x in items}
        self.groups = len(self.parent)            # every element starts alone

    def add(self, x):
        if x not in self.parent:
            self.parent[x] = x
            self.size[x] = 1
            self.groups += 1

    def find(self, x):
        self.add(x)
        root = x
        while self.parent[root] != root:          # pass 1: climb to the root
            root = self.parent[root]
        while self.parent[x] != root:             # pass 2: bend the trail flat
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                          # already together - nothing to do
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra                       # the SMALLER circle joins the bigger
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        self.groups -= 1
        return True

    def connected(self, a, b):
        return self.find(a) == self.find(b)

    def circles(self):
        out = {}
        for x in self.parent:
            out.setdefault(self.find(x), []).append(x)
        return {r: sorted(v) for r, v in out.items()}


friendships = [
    ("Nikhil", "Priya"), ("Priya", "Aisha"), ("Aisha", "Dan"), ("Dan", "Nikhil"),
    ("Marco", "Lena"),   ("Lena", "Jo"),     ("Jo", "Ben"),    ("Ben", "Marco"),
    ("Sofia", "Theo"),   ("Theo", "Sofia"),
]
guests = sorted({p for pair in friendships for p in pair})

uf = UnionFind(guests)
print("guests:", len(guests), "- so", uf.groups, "circles before anyone speaks")

merged = 0
for a, b in friendships:
    did = uf.union(a, b)
    merged += did
    print(f"  union({a:6}, {b:6}) -> {'merged' if did else 'already together'};"
          f" circles now {uf.groups}")

print("\ncircles:", uf.groups)
for root, members in sorted(uf.circles().items()):
    print(f"  {root:6}: {members}")

print("\nintroductions that changed anything:", merged, "of", len(friendships))
print("the rest closed a cycle - Kruskal's exact reject test")
print("Dan ~ Priya?", uf.connected("Dan", "Priya"),
      " Dan ~ Ben?", uf.connected("Dan", "Ben"))

print("\nAisha turns round and introduces Marco:")
uf.union("Aisha", "Marco")
print("  circles now:", uf.groups)
print("  Dan ~ Ben?", uf.connected("Dan", "Ben"))
for root, members in sorted(uf.circles().items()):
    print(f"  {root:6}: {members}")
print("  parent, fully compressed:", uf.parent)

# ---------------- OUTPUT, verbatim (CPython 3.12.7) ----------------
# guests: 10 - so 10 circles before anyone speaks
#   union(Nikhil, Priya ) -> merged; circles now 9
#   union(Priya , Aisha ) -> merged; circles now 8
#   union(Aisha , Dan   ) -> merged; circles now 7
#   union(Dan   , Nikhil) -> already together; circles now 7
#   union(Marco , Lena  ) -> merged; circles now 6
#   union(Lena  , Jo    ) -> merged; circles now 5
#   union(Jo    , Ben   ) -> merged; circles now 4
#   union(Ben   , Marco ) -> already together; circles now 4
#   union(Sofia , Theo  ) -> merged; circles now 3
#   union(Theo  , Sofia ) -> already together; circles now 3
#
# circles: 3
#   Marco : ['Ben', 'Jo', 'Lena', 'Marco']
#   Nikhil: ['Aisha', 'Dan', 'Nikhil', 'Priya']
#   Sofia : ['Sofia', 'Theo']
#
# introductions that changed anything: 7 of 10
# the rest closed a cycle - Kruskal's exact reject test
# Dan ~ Priya? True  Dan ~ Ben? False
#
# Aisha turns round and introduces Marco:
#   circles now: 2
#   Dan ~ Ben? True
#   Nikhil: ['Aisha', 'Ben', 'Dan', 'Jo', 'Lena', 'Marco', 'Nikhil', 'Priya']
#   Sofia : ['Sofia', 'Theo']
#   parent, fully compressed: {'Aisha': 'Nikhil', 'Ben': 'Nikhil', 'Dan': 'Nikhil', 'Jo': 'Nikhil', 'Lena': 'Nikhil', 'Marco': 'Nikhil', 'Nikhil': 'Nikhil', 'Priya': 'Nikhil', 'Sofia': 'Sofia', 'Theo': 'Sofia'}

Thirteen structures down — arrays, lists, stacks, queues, deques, hash maps, matrices, trees, BSTs, heaps, tries, graphs, and this connectivity specialist. Each was the right answer to one access pattern. The last chapter steps back and turns that whole collection into a single decision: given a new problem, how do you pick the right container on sight? Next: the chooser's map — matching the operation you do most to the structure that makes it cheap. →

PROGRAMS run them line by line — the same ideas, written the many ways Python offers
Chapter 61, in working code

Here's the container that answers "are these two things connected?" not by re-walking a maze but by giving every group a single name — and we'll build it from one flat array of integers, then watch two tiny tricks make it so fast the cost has a famous, almost unbelievable name.

The parent array — a forest in a flat array
Every element stores one number: the index of its parent. Roots point at themselves, and a root's index IS its group's label — the whole forest is one contiguous run of integers you index into.
find and union — climb, then repoint a root
find(x) climbs to the root; union(a,b) finds both roots and, if they differ, staples one under the other with a single array write. Correct and tiny — but a blind union can grow an O(n) comb.
Path compression — flatten the trail on the way up
You already walk the path to the root to answer a query — so bend every node you pass straight at the root. A tall chain becomes a flat bush after one find; path halving does the same in a single pass and is what production libraries ship.
Union by size — keep the trees short
At merge time, always hang the smaller tree under the larger root. One extra size array and one comparison cap every tree's height at O(log n), so it can never grow into the comb.
Union-Find at work — components, cycles, islands
The payoff. Counting connected components, catching the edge that closes a cycle (Kruskal's exact trick), and counting islands in a grid — each one a near-linear sweep over the same flat parent array.
end of chapter 61 · six sections
iolinked
designed & developed by Ajai Raj
Python, from the metal up · a product of iolinked