Find & Union

Two operations, four lines each. What makes them worth a page is that the naive version of both is O(n), the optimized version is effectively O(1), and the gap between them is closed by two independent tricks that most people learn as a single incantation. This page separates them, shows what each one alone buys, and gives you a sandbox to switch either off and watch the structure degrade.

Prerequisite: The Idea - the forest, the representative, and the invariants.

1. `find`: walk up until the parent is yourself

def find(self, element):
    while self.parent[element] != element:
        element = self.parent[element]
    return element

That is the whole operation, and it is correct: invariant 1 guarantees the loop terminates. Its cost is the depth of element, so the interesting question is how deep a tree can get.

Badly. Union two singletons, then union the result with a third singleton by always hanging the second root under the first, and after n merges you have a straight chain. find on its bottom now walks n - 1 hops.

The degenerate case: n merges done carelessly give a chain, and find(4) pays 4 hops every single call.

2. Path compression: pay once, never again

The chain is only expensive because you keep re-walking it. So on the way back from the root, rewire every node you passed to point straight at the root. The walk you just did is the last time anybody pays for it.

def find(self, element):
    if self.parent[element] == element:
        return element
    self.parent[element] = self.find(self.parent[element])
    return self.parent[element]

The recursion is doing two jobs at once: the descent finds the root, and the assignment on the way back up flattens the path. A find on a chain of length k costs k and leaves behind a tree where every one of those k nodes is now at depth 1.

1 / 6

Variant	What it does
Variant	When to prefer it
Full compression (recursive)	every node on the path is rewired to the root
Full compression (recursive)	The default, and what interviewers expect. Costs a recursion frame per hop.
Path halving (iterative)	`parent[x] = parent[parent[x]]` while walking; each node skips to its grandparent
Path halving (iterative)	Same asymptotic bound, no recursion, one pass. The right choice when `n` is large enough that the recursion depth is a real risk.
Path splitting	like halving, but points `x` at its grandparent before advancing to the old parent
Path splitting	Equivalent in practice; mentioned here only so the name is not a surprise.

The iterative form worth actually memorising, because it is shorter than the recursive one and cannot blow the stack:

def find(self, x):
    while self.parent[x] != x:
        self.parent[x] = self.parent[self.parent[x]]   # halve the path
        x = self.parent[x]
    return x

Compression must write to the caller's own entry

self.parent[element] = self.find(...) - the assignment target is the node you were called on, not a local. Writing find(self.parent[element]) and returning it without the assignment is a working find that compresses nothing: correct answers, zero speedup, and no symptom other than a timeout on the large test case. This is the single most common DSU bug, precisely because the broken version passes every correctness test.

Compression mutates during a read

find is not a read-only operation. It writes to parent. That matters in three places: you cannot call it while iterating parent and assuming stability, you cannot share one DSU across threads without a lock, and a "query" in a problem statement may be doing real work. It is also why rollback DSU has to give compression up entirely.

3. `union`: join the two roots, not the two nodes

def union(self, a, b):
    root_a, root_b = self.find(a), self.find(b)
    if root_a == root_b:
        return False          # already together
    self.parent[root_b] = root_a
    self.count -= 1
    return True

Three things in four lines are worth naming:

You attach roots, never the arguments. parent[b] = a would be a catastrophe: it detaches b's entire subtree from b's old root and silently splits that group in two. Invariant 5 is broken and nothing complains.
The root_a == root_b case is not an error. It means the fact you were just given was already implied by earlier facts. Returning False from it is free information - see section 6.
count drops only when a real merge happens. Decrementing unconditionally is the standard off-by-a-few bug in component counting.

4. Union by rank, union by size

Left to itself, union always hangs root_b under root_a, which is exactly how you build the chain from section 1. The fix is to make the shallower or smaller tree the one that gets hung.

Same two trees, both merge orders. Attaching the taller tree under the shorter one adds a level; the other way round adds none.

The key observation: hanging the shorter tree under the taller root does not increase the height at all, unless the two heights were equal. That is why rank only ever increments in the tie case.

def union(self, a, b):
    ra, rb = self.find(a), self.find(b)
    if ra == rb:
        return False
    if self.rank[ra] < self.rank[rb]:
        ra, rb = rb, ra              # ensure ra is the taller (or tied) root
    self.parent[rb] = ra
    if self.rank[ra] == self.rank[rb]:
        self.rank[ra] += 1           # only a tie can grow the height
    self.count -= 1
    return True

1 / 13

Union by size is the same idea with a different key: attach the root of the smaller population under the larger. It bounds height at log2(n) too, by a different argument - every time an element's depth increases, the tree it lives in has at least doubled, so no element's depth can increase more than log2(n) times.

Rule	Bounds height because
Rule	Choose it when
By rank	a rank-`r` tree needs at least `2^r` nodes, so rank never exceeds `log2(n)`
By rank	You do not need component sizes anyway. One extra array, values stay tiny.
By size	a node's depth grows only when its tree doubles, so at most `log2(n)` times
By size	You need `size` for the answer regardless (largest component, "how many in this group") - then rank is a second array buying nothing. Also the only option if you need rollback.

Mnemonic

If the problem ever asks "how big", use union by size and skip rank entirely. The two rules give the same asymptotic guarantee, so carrying both is pure overhead. Rank is the textbook default; size is the one that more often pays for itself.

Rank is not height once compression is on

Union by rank and path compression interfere, and that is fine. Compression makes trees shorter without touching any rank, so after a few finds a root's rank overstates its real height. Nobody corrects this - the bound height <= rank stays true, which is all union-by-rank needs, and recomputing true heights would cost more than the imbalance ever does. Do not "fix" a rank you notice is too high.

5. Why the two together are effectively constant

Each optimization alone gets you to O(log n). Both together give O(a(n)) amortized per operation, where a is the inverse Ackermann function - and it is bounded by 4 for any n you could ever allocate.

Compression	Balancing	Per operation	In practice
off	off	`O(n)`	A chain. Times out on any real input.
on	off	`O(log n)` amortized	Fine. Compression alone does most of the work.
off	on	`O(log n)` worst case	Fine, and the worst case rather than amortized - which is why rollback DSU settles here.
on	on	`O(a(n))` amortized	Under 5 pointer hops for `n` beyond the number of atoms in the universe. Treat as `O(1)`.

The a(n) bound is amortized, not worst case

One individual find can still be slow. The O(a(n)) figure is an average over a sequence of operations; a single find immediately after a long chain was built still walks that chain - it just never does so twice. This matters only if you are bounding the latency of one call rather than the total, which no interview problem asks for and some real-time systems do.

For quoting a complexity in an interview: m operations on n elements cost O(m * a(n)), and you may say "effectively O(m)." For Kruskal the whole DSU part vanishes next to the O(E log E) sort.

6. The return value is free cycle detection

union returning False means: a and b were already connected before this fact arrived. On an undirected graph fed edge by edge, that is exactly the statement this edge closes a cycle.

`union(u, v)` returns	Reading it as a graph	Problems built on it
`True`	the edge joins two separate components - it is a tree edge	Kruskal's MST keeps exactly these
`False`	both endpoints already connected - the edge closes a cycle	Redundant Connection, Graph Valid Tree, cycle detection

Which gives three one-liners you should be able to write without thinking:

# 1. Does this undirected graph contain a cycle?
has_cycle = any(not dsu.union(u, v) for u, v in edges)
 
# 2. Is this a valid tree? (connected AND acyclic)
is_tree = len(edges) == n - 1 and all(dsu.union(u, v) for u, v in edges)
 
# 3. How many connected components?
for u, v in edges:
    dsu.union(u, v)
components = dsu.count

any and all short-circuit, which changes the DSU state

Both one-liners above stop early, leaving the DSU half-built. That is correct for the boolean they return and wrong if you then read dsu.count. When you need the answer and the final structure, write the explicit loop.

7. Sandbox: switch the optimizations off

Ten elements. Pick a node, then a second one to union them; pick the same node twice to run find on it. The two toggles are the point: with both off, hit "+4 random unions" a few times and watch max depth and pointer hops climb. Turn them back on and the same forest flattens to depth 1.

components10

max depth0

pointer hops0

Click a node, then another, to union them.

pick:

Three things to try:

Both off. Union 0-1, 1-2, 2-3, 3-4 in that order. With no balancing rule, each new root swallows the old one and you get the chain from section 1, rooted at 4. Now find(0) repeatedly: every call costs the same 4 hops.
Compression back on. find(0) once. Max depth collapses to 1, and the next find(0) costs a single hop forever after.
Rank on, compression off. Try to build the same chain - you cannot. The rank rule refuses to stack a taller tree under a shorter root, so depth never gets past 1 here.

8. The reference implementation

This is the version to write from memory: union by rank and by size (because problems ask for sizes), path compression, a live component count, and a union whose return value you can branch on.

class DisjointSets:
    def __init__(self, size):
        self.parent = list(range(size))  # each element is its own root initially
        self.rank = [0] * size  # upper bound on tree height per root
        self.size = [1] * size  # component size (1 per node initially)
        self.count = size  # number of disjoint components
 
    def find(self, element):
        if self.parent[element] == element:
            return element
        # path compression: flatten the chain to the root on the way back
        self.parent[element] = self.find(self.parent[element])
        return self.parent[element]
 
    def union(self, a, b):
        root_a = self.find(a)
        root_b = self.find(b)
        if root_a != root_b:
            # union by rank: attach shorter tree under taller to keep height small
            if self.rank[root_a] > self.rank[root_b]:
                self.parent[root_b] = root_a
                self.size[root_a] += self.size[root_b]
            elif self.rank[root_a] < self.rank[root_b]:
                self.parent[root_a] = root_b
                self.size[root_b] += self.size[root_a]
            else:
                self.parent[root_b] = root_a
                self.size[root_a] += self.size[root_b]
                self.rank[root_a] += 1  # only grows when both trees have equal rank
            self.count -= 1
            return True  # merged: two components became one
        return False  # already connected: no merge happened
 
    def getCount(self):
        return self.count
 
    def getSize(self, a):
        return self.size[self.find(a)]
 
    def getSizes(self):
        for i in range(len(self.parent)):
            if self.parent[i] == i:
                yield self.parent[i], self.size[i]

Next: Metadata - what else you can carry on the roots for free, and the one rule that keeps it correct.

1. find: walk up until the parent is yourself​

2. Path compression: pay once, never again​

3. union: join the two roots, not the two nodes​

4. Union by rank, union by size​

5. Why the two together are effectively constant​

6. The return value is free cycle detection​

7. Sandbox: switch the optimizations off​

8. The reference implementation​