Union-Find (Disjoint Set) in Python: Tracking Connected Things Fast

You are wiring up a network of 100,000 machines. Cables get plugged in one at a time, and after each one somebody asks the same question: can machine 4,213 reach machine 91,006? Answering that with a graph search costs O(V + E) every time you ask, so a thousand questions on that network is a few hundred million steps. Union-find answers each one by following, on average, less than one pointer.

The structure is about twenty lines of Python and it stores one integer per element. What makes it worth studying is the gap between the obvious implementation and the good one. The obvious version is O(n) per query. Two changes, each about two lines, take it to O(α(n)) amortised — where α is the inverse Ackermann function, the slowest-growing function that appears in any complexity bound you will meet. For every n that fits in this universe, α(n) is at most 4.

Two honest caveats before you get attached to it. That bound is amortised across a sequence of operations, not a promise about any single one; a lone find can still cost O(log n). And union-find only ever merges. There is no way to unplug a cable. Both of those decide when it is the right tool and when it is not.

The idea

The problem is called disjoint set union, and it has exactly three operations:

• make_set(n) — start with n elements, each alone in its own set.
• find(x) — return a name for the set that contains x.
• union(a, b) — merge the set containing a with the set containing b.

connected(a, b) is not a fourth operation. It is find(a) == find(b) — if two elements report the same set name, they are in the same set. The whole design problem is choosing how to name a set.

The first idea most people have is to store a label per element: element 7 is in group 2, element 8 is in group 2, element 9 is in group 5. find is then one array read, which is as fast as it gets. But merging group 2 into group 5 means finding and rewriting every element labelled 2, which is a full O(n) scan. Building up n − 1 merges that way costs O(n²), and on 100,000 machines that is five billion writes.

The second idea is to keep a list of members per set. Merging two lists is O(size of the smaller one), which is better, but now find has no answer at all without a second structure mapping each element back to its set.

Union-find takes a third route. Name the set after one of its members — call it the representative — and have every other member store a pointer to some other member that is closer to the representative. Each set becomes a tree; the collection of sets is a forest. The representative is the root, and a root is recognised by pointing at itself.

All of that fits in a single flat list. parent[i] holds the parent of element i, and parent[r] == r means r is a root. There is no member list, no set object, no dictionary of groups — just n integers.

The two operations fall straight out of that picture:

• find(x) follows parent upwards until it reaches an element that is its own parent, and returns it.
• union(a, b) finds both roots. If they are the same, the elements were already together and there is nothing to do. Otherwise it writes one pointer: one root now points at the other, and two trees become one.

union does one write. Every cost in this structure therefore comes from find, and find costs one step per level of the tree. So the entire performance question is: how deep do these trees get? The rest of the post is that question and its two answers.

Watching it work

Take eight machines numbered 0 to 7 and plug in six cables, in this order: 0-1, 2-3, 1-3, 4-5, 6-7, 5-7. Start with parent = [0, 1, 2, 3, 4, 5, 6, 7], every element its own root, eight separate sets.

Cable 0-1. find(0) is 0, find(1) is 1. Different roots, so link them: write parent[0] = 1. Element 0 is no longer a root; the set is now named 1.

Cable 2-3. Same story one level over: parent[2] = 3.

Cable 1-3. find(1) walks nowhere — 1 is already a root. find(3) is 3. Different, so parent[1] = 3. Notice what this did to element 0: it never moved, but it is now two hops from its root, because the root it pointed at got a parent of its own.

Cables 4-5 and 6-7 mirror the first two: parent[4] = 5, parent[6] = 7.

Cable 5-7. find(5) is 5, find(7) is 7, so parent[5] = 7.

Six cables, six writes, and parent is now [1, 3, 3, 3, 5, 7, 7, 7]. That is exactly the forest in the first diagram: one tree rooted at 3 holding 0, 1, 2, 3, and one rooted at 7 holding 4, 5, 6, 7.

Now ask questions. Is 0 connected to 2? find(0) walks 0 to 1 to 3 and stops; find(2) walks 2 to 3 and stops. Same root, so yes — even though no cable ever directly joined them. Is 0 connected to 4? Roots 3 and 7, so no.

Plug in one more cable, 3-5. find(3) is 3, find(5) walks to 7. Write parent[3] = 7 and all eight machines are one network. Try cable 3-5 again and both finds return 7, so union does nothing and reports that the two were already together. That "already together" answer is not a wasted call — it is the cycle test that Kruskal's algorithm is built on.

The code

The naive version

This is the algorithm exactly as described, with no cleverness at all.

class NaiveDisjointSet:
    """Union-find with no balancing: union hangs one root under the other.

    Every element stores exactly one integer, the index of its parent. An
    element that is its own parent is a root, and the root is the name of
    the set. Nothing else is stored: there is no member list anywhere.
    """

    def __init__(self, size: int) -> None:
        self.parent = list(range(size))

    def find(self, item: int) -> int:
        """Walk parent pointers until reaching an item that is its own parent."""
        while self.parent[item] != item:
            item = self.parent[item]
        return item

    def union(self, a: int, b: int) -> bool:
        """Merge two sets. Returns False if they were already the same set."""
        root_a, root_b = self.find(a), self.find(b)
        if root_a == root_b:
            return False
        # The whole merge is one write: a's root now reports to b's root.
        self.parent[root_a] = root_b
        return True

    def connected(self, a: int, b: int) -> bool:
        return self.find(a) == self.find(b)


cables = NaiveDisjointSet(8)
for a, b in [(0, 1), (2, 3), (1, 3), (4, 5), (6, 7), (5, 7)]:
    cables.union(a, b)
    print(f"union({a}, {b}) -> parent = {cables.parent}")

print("connected(0, 2):", cables.connected(0, 2))
print("connected(0, 4):", cables.connected(0, 4))
print("union(3, 5) merged them:", cables.union(3, 5))
print("parent =", cables.parent)
print("union(3, 5) again:", cables.union(3, 5))

union(0, 1) -> parent = [1, 1, 2, 3, 4, 5, 6, 7]
union(2, 3) -> parent = [1, 1, 3, 3, 4, 5, 6, 7]
union(1, 3) -> parent = [1, 3, 3, 3, 4, 5, 6, 7]
union(4, 5) -> parent = [1, 3, 3, 3, 5, 5, 6, 7]
union(6, 7) -> parent = [1, 3, 3, 3, 5, 5, 7, 7]
union(5, 7) -> parent = [1, 3, 3, 3, 5, 7, 7, 7]
connected(0, 2): True
connected(0, 4): False
union(3, 5) merged them: True
parent = [1, 3, 3, 7, 5, 7, 7, 7]
union(3, 5) again: False

Line for line, that is the walkthrough above. Twenty lines of code, and it is already correct — it will answer every connectivity question you throw at it.

Where it falls apart

It is correct, not fast. The union above always hangs a's root under b's root, no matter what those trees look like, and an input can exploit that.

Here is the input: union(0, 1), then union(1, 2), then union(2, 3), and so on up the line. Each call takes the tree built so far and hangs the whole thing under a brand-new single element. Nothing branches. You get one chain.

def pointer_hops(parent: list[int], item: int) -> int:
    """How many parent pointers separate this item from the root of its tree."""
    hops = 0
    while parent[item] != item:
        item = parent[item]
        hops += 1
    return hops


chain = NaiveDisjointSet(6)
for node in range(5):
    chain.union(node, node + 1)

print("parent:", chain.parent)
print("find(0) follows", pointer_hops(chain.parent, 0), "pointers")

for size in [10, 100, 1000]:
    line = NaiveDisjointSet(size)
    for node in range(size - 1):
        line.union(node, node + 1)
    total = sum(pointer_hops(line.parent, item) for item in range(size))
    print(f"n = {size:>4}: one find() per item follows {total:>6} pointers in total")

parent: [1, 2, 3, 4, 5, 5]
find(0) follows 5 pointers
n =   10: one find() per item follows     45 pointers in total
n =  100: one find() per item follows   4950 pointers in total
n = 1000: one find() per item follows 499500 pointers in total

Count it directly. In a chain of n elements the element at the bottom is n − 1 pointers from the root, the next one up is n − 2, and so on. One find per element costs 0 + 1 + … + (n − 1), which is n(n − 1) / 2. For n = 1000 that is 499,500, exactly what printed. A single find is O(n), and m operations cost O(mn) — no better than the label-rewriting approach this structure was supposed to beat.

Union by size

The chain forms because union links blindly. Give it a rule instead: keep the number of elements in each tree, and always hang the smaller tree under the larger tree's root.

Look at what that changes at the third cable of the degenerate sequence, where a three-element tree meets a lone element.

Linking the big tree under the lone element pushes all three of its elements down a level. Linking the lone element under the big root pushes exactly one element down a level, and the big tree's depth does not change at all. Same merge, same result set, wildly different shape.

That rule gives a real bound, and the argument is short. An element only gets deeper when the root of its tree is hung under another root — and by the rule, that only happens when the other tree is at least as big. So every time an element's depth goes up by one, the tree it lives in at least doubles in size. A tree starts at size 1 and can never exceed n, so it can double at most log₂ n times. No element is ever more than log₂ n pointers from its root. With 100,000 elements log₂ n is 16.6, so no element ever sits more than 16 pointers deep — depth 17 would need a tree of 131,072 elements.

Some implementations track rank — an upper bound on the tree's height — instead of size, and hang the lower-rank root under the higher-rank one. The asymptotics are identical. Size is easier to reason about and gives you the size of every component for free, so this post uses size.

Path compression

Union by size limits how deep a tree can get. Path compression attacks the problem from the other end: it fixes the paths you actually walk.

When find(x) walks from x up to the root, it learns the root of every single element on that path. Throwing that away is wasteful. So walk the path twice — once up to find the root, once again to re-point every element on it directly at the root.

The second walk costs the same as the first, so a find gets at most twice as expensive. In exchange, every element on that path now sits one hop from the root, and every subtree hanging off one of them rises by the same number of levels its parent did. The work is not saved for this call; it is saved for all the calls after it. That is why the bound that comes out is amortised.

The whole thing

Both rules together, in the form you should actually write:

class DisjointSet:
    """Union-find with union by size and full path compression.

    parent[i] is i's parent, size[r] is the number of elements in the tree
    rooted at r (only meaningful when r really is a root), and count is how
    many separate sets are left.
    """

    def __init__(self, size: int) -> None:
        self.parent = list(range(size))
        self.size = [1] * size
        self.count = size

    def find(self, item: int) -> int:
        """Return the root of item's set, flattening the path on the way back."""
        root = item
        while self.parent[root] != root:
            root = self.parent[root]

        # Second walk over the same path: every item on it now points straight
        # at the root, so the next find on any of them costs a single hop.
        while self.parent[item] != root:
            next_item = self.parent[item]
            self.parent[item] = root
            item = next_item
        return root

    def union(self, a: int, b: int) -> bool:
        """Merge two sets. Returns False if they were already the same set."""
        root_a, root_b = self.find(a), self.find(b)
        if root_a == root_b:
            return False

        # Always hang the smaller tree under the larger root, so the elements
        # that gain a level are the ones in the smaller half.
        if self.size[root_a] < self.size[root_b]:
            root_a, root_b = root_b, root_a
        self.parent[root_b] = root_a
        self.size[root_a] += self.size[root_b]
        self.count -= 1
        return True

    def connected(self, a: int, b: int) -> bool:
        return self.find(a) == self.find(b)

Run the same six cables through it and the shape of the forest changes completely:

balanced = DisjointSet(8)
for a, b in [(0, 1), (2, 3), (1, 3), (4, 5), (6, 7), (5, 7)]:
    balanced.union(a, b)
    print(f"union({a}, {b}) -> parent = {balanced.parent}")

print("sets left:", balanced.count)
print("connected(0, 3):", balanced.connected(0, 3), "-> parent =", balanced.parent)
print("connected(4, 7):", balanced.connected(4, 7), "-> parent =", balanced.parent)

union(0, 1) -> parent = [0, 0, 2, 3, 4, 5, 6, 7]
union(2, 3) -> parent = [0, 0, 2, 2, 4, 5, 6, 7]
union(1, 3) -> parent = [0, 0, 0, 2, 4, 5, 6, 7]
union(4, 5) -> parent = [0, 0, 0, 2, 4, 4, 6, 7]
union(6, 7) -> parent = [0, 0, 0, 2, 4, 4, 6, 6]
union(5, 7) -> parent = [0, 0, 0, 2, 4, 4, 4, 6]
sets left: 2
connected(0, 3): True -> parent = [0, 0, 0, 0, 4, 4, 4, 6]
connected(4, 7): True -> parent = [0, 0, 0, 0, 4, 4, 4, 4]

Two things to notice. The roots are now 0 and 4 rather than 3 and 7, because ties in size keep the first root. And the last two lines are path compression caught in the act: connected(0, 3) walked 3 to 2 to 0, so parent[3] became 0; connected(4, 7) walked 7 to 6 to 4, so parent[7] became 4. Neither query changed which sets exist. Both made the next query cheaper.

Now feed the degenerate sequence — the one that produced a 999-link chain — to both versions:

naive_line = NaiveDisjointSet(1000)
balanced_line = DisjointSet(1000)
for node in range(999):
    naive_line.union(node, node + 1)
    balanced_line.union(node, node + 1)

print("naive    deepest:", max(pointer_hops(naive_line.parent, i) for i in range(1000)))
print("balanced deepest:", max(pointer_hops(balanced_line.parent, i) for i in range(1000)))

naive    deepest: 999
balanced deepest: 1

The adversarial input that made the naive structure quadratic produces a completely flat tree here: every one of the 1,000 elements points straight at the root.

How the code maps to the idea

self.parent = list(range(size)) is the whole make_set step. Element i starts as its own parent, which by the root test means every element starts alone in a set of one. That is O(n) once, and together with self.size it is the only allocation the structure ever makes — no operation allocates anything.

The first loop in find is the walk from the diagram — climb until parent[root] == root. It is written iteratively on purpose. The recursive version reads beautifully and blows up in Python: build a naive chain of 10,000 elements and the first find exceeds the default recursion limit of 1,000 and raises RecursionError. Iteration has no such ceiling.

The second loop in find is path compression, and it is careful about one thing: it saves next_item before overwriting self.parent[item]. Overwrite first and you have destroyed the link you were about to follow, and the loop reads the root's parent forever.

if root_a == root_b: return False is the guard that makes union idempotent, and the return value is genuinely useful. True means "these were two separate sets and I merged them"; False means "these were already connected". In an undirected graph, False means the edge you just offered closes a cycle. That single boolean is the entire cycle test in Kruskal's algorithm.

The size swap in union is a trick worth reading twice. Rather than branching on which root to write, it relabels the roots so root_a is always the bigger one, then writes unconditionally. Ties go to root_a, which is why the earlier trace kept 0 and 4 as roots.

self.count is free bookkeeping. Start it at n, drop it by one on every successful merge, and it always holds the number of connected components. Getting that from the parent list instead would cost an O(n) scan.

Edge cases need no special code. union(x, x) finds the same root twice and returns False. find on a root returns immediately: the first loop never runs, and the second loop's condition self.parent[item] != root is already false. A structure built with size 0 holds two empty lists and a count of 0, and there is no valid element to pass to anything — also correct.

Non-integer elements are the one thing the code cannot do as written, because parent is a list indexed by element. The fix is a dictionary built once — map each label to a position with dict(zip(labels, range(len(labels)))), run the structure on the integers, and translate back at the end. Doing it this way keeps every operation on a flat list of machine integers, which is much faster in Python than a dict-backed parent.

Complexity

Everything the structure does is find, so start there. Both optimisations exist to control tree depth, and they do it in different ways.

Union by size bounds the depth at log₂ n. The argument from earlier, restated as a count: an element's depth increases only when its root is linked under another root, which only happens when the other tree is at least as large, so the element's tree at least doubles. Doubling from 1 cannot happen more than log₂ n times before the tree exceeds n elements. Watch it happen on inputs designed to be as bad as possible for a size-balanced structure — merge pairs, then pairs of pairs, and so on, so that every merge joins two equal-sized trees:

class SizeOnlyDisjointSet(DisjointSet):
    """Union by size, but find() never compresses — to expose the log n depth."""

    def find(self, item: int) -> int:
        while self.parent[item] != item:
            item = self.parent[item]
        return item


for exponent in [4, 10, 16]:
    total_items = 2 ** exponent
    tournament = SizeOnlyDisjointSet(total_items)
    step = 1
    while step < total_items:
        for start in range(0, total_items, step * 2):
            tournament.union(start, start + step)
        step *= 2
    deepest = max(pointer_hops(tournament.parent, i) for i in range(total_items))
    print(f"n = {total_items:>6}: deepest item sits {deepest} pointers from its root")

n =     16: deepest item sits 4 pointers from its root
n =   1024: deepest item sits 10 pointers from its root
n =  65536: deepest item sits 16 pointers from its root

Four, ten and sixteen are log₂ 16, log₂ 1024 and log₂ 65536. The bound is not an approximation; it is met exactly by this input.

Path compression alone gives O(log n) amortised. Without balancing, a chain of n can still form, so a single find on it costs n — but that find flattens the chain, and rebuilding a path that deep takes a fresh run of unions to pay for it. Spread across a sequence of m operations the cost per operation works out at O(log n).

Together they give O(α(n)) amortised, which is Tarjan's 1975 result: any sequence of m operations on n elements costs O(m α(m, n)) total. The proof is a page of potential-function accounting and is out of scope here, but the shape of it is that compression keeps destroying the structure that would let deep paths recur, and union by size keeps the depth low enough that compression has short work to do. Neither alone reaches α; the two compose because they attack different halves of the problem.

About α. The Ackermann function grows faster than any function you can build from addition, multiplication and exponentiation stacked in a loop. α is its inverse, so it grows slower than any of those inverses — slower than log n, slower than log log n, slower than the number of times you can take a logarithm before reaching 1. Under the standard definition, α(n) does not reach 5 until n is larger than a tower of powers of two thousands of levels tall, a number vastly beyond the roughly 10⁸⁰ atoms in the observable universe. For any input you can physically store, α(n) is at most 4.

That is why people say "effectively constant". It is not constant, and the distinction matters twice. First, the bound is amortised: individual operations vary, and a single find can still walk O(log n) pointers before compression flattens the path. Second, the α is not slack in the analysis — Fredman and Saks proved in 1989 that Ω(α(n)) amortised time per operation is a lower bound for any implementation in the cell-probe model. Nobody is going to find the O(1) version, because there is not one.

In practice the constant is tiny. Here are 200,000 union calls over 100,000 elements, with every pointer that find follows counted:

class CountingDisjointSet(DisjointSet):
    """The same structure, but it records every parent pointer find() follows."""

    def __init__(self, size: int) -> None:
        super().__init__(size)
        self.hops = 0

    def find(self, item: int) -> int:
        root = item
        while self.parent[root] != root:
            root = self.parent[root]
            self.hops += 1
        while self.parent[item] != root:
            next_item = self.parent[item]
            self.parent[item] = root
            item = next_item
        return root


def pseudo_pairs(count: int, limit: int) -> list[tuple[int, int]]:
    """A fixed, machine-independent stream of pairs.

    A hand-rolled linear congruential generator rather than random.random(),
    so the numbers printed below are identical every time anyone runs this.
    """
    state = 88172645463325252
    pairs = []
    for _ in range(count):
        drawn = []
        for _ in range(2):
            state = (state * 6364136223846793005 + 1442695040888963407) % (1 << 64)
            drawn.append((state >> 33) % limit)
        pairs.append((drawn[0], drawn[1]))
    return pairs


items = 100_000
measured = CountingDisjointSet(items)
operations = pseudo_pairs(200_000, items)
for a, b in operations:
    measured.union(a, b)

finds = 2 * len(operations)
print(f"{len(operations):,} unions over {items:,} items")
print(f"sets left: {measured.count:,}")
print(f"total pointers followed by {finds:,} find() calls: {measured.hops:,}")
print(f"average per find: {measured.hops / finds:.2f}")

200,000 unions over 100,000 items
sets left: 1,885
total pointers followed by 400,000 find() calls: 347,866
average per find: 0.87

Under one pointer per find, averaged over 400,000 calls. The breakdown is worth reading: 30% of those finds cost nothing at all, because the element handed in is already a root; 56% cost exactly one hop, because the element already points straight at its root; and the deepest find in the entire run walks five pointers. Give the same 400,000 finds to the naive structure on its worst case — the chain of 100,000 elements from earlier — and the average element sits 50,000 pointers from its root, so the same work costs roughly 20 billion hops.

Space is O(n): one parent integer and one size integer per element, and both lists are allocated once at construction. There is no per-operation allocation at all, which is a large part of why the structure is fast in practice as well as on paper.

When to use it, and when not to

Use it when merges arrive over time and you keep asking whether two things are in the same group. That is the exact shape union-find fits: an equivalence relation that only ever grows. Kruskal's algorithm, cycle detection while reading edges, counting connected components as a graph is built, grouping records that share any identifier — all the same problem.

Do not use it when edges can be removed. This is the big one. There is no split, and path compression has thrown away the history you would need to undo a merge. If your graph loses edges as well as gaining them, you need a proper dynamic connectivity structure — the Holm, de Lichtenberg and Thorup structure gives O(log² n) amortised per update — or you process the whole query stream offline in reverse, so deletions become insertions and union-find works again.

If you need undo but not arbitrary deletion, there is a middle path: keep union by size, drop path compression, and push each (root, old_size) pair onto a stack so undo() can pop it back. Without compression the depth bound is still log₂ n, so every operation costs O(log n) rather than O(α(n)). That is the standard trick behind offline dynamic connectivity, and it is a fair trade when rollback is what you need.

Do not use it when you need the path, not just the fact of connection. Union-find can tell you machine 4,213 reaches machine 91,006; it cannot tell you which cables to follow, because parent pointers are an artefact of merge order and have nothing to do with the real edges. For a route, use breadth-first search.

Do not use it for directed reachability. Union-find models an equivalence relation: symmetric and transitive. A one-way edge is neither. Reachability in a directed graph needs a search or a strongly-connected-components algorithm.

Do not reach for it when one static graph gets one question. A single depth-first search labels every component in O(V + E) and needs no extra structure. Union-find earns its keep when the graph is arriving incrementally, or when queries are interleaved with merges.

Also worth knowing: Python's standard library has no disjoint-set type. This is one of the classic structures you do have to write yourself, which is fine, because the whole thing is twenty lines. If you already depend on networkx, networkx.utils.UnionFind is there; if you have scipy and only want components of a static graph, scipy.sparse.csgraph.connected_components does it in C.

Where it shows up in the real world

Kruskal's minimum spanning tree algorithm is the classic. Sort every edge by weight, then walk the sorted list and accept an edge only if its endpoints are in different components — which is exactly union returning True. Without union-find you would need a graph search per edge to check for a cycle, and the algorithm would be O(E · V) rather than O(E log E).

def kruskal(node_count: int,
            edges: list[tuple[int, int, int]]) -> tuple[list[tuple[int, int]], int]:
    """Cheapest set of edges connecting every node, rejecting cycles with union-find."""
    forest = DisjointSet(node_count)
    chosen: list[tuple[int, int]] = []
    total = 0

    for weight, a, b in sorted(edges):
        # union() returns False exactly when a and b already share a root, so
        # this one call is the cycle test. No graph search anywhere.
        if forest.union(a, b):
            chosen.append((a, b))
            total += weight
            if len(chosen) == node_count - 1:
                break

    return chosen, total


road_costs = [(4, 0, 1), (3, 0, 2), (1, 1, 2), (2, 1, 3),
              (4, 2, 3), (2, 3, 4), (6, 4, 5), (3, 3, 5)]
tree_edges, tree_weight = kruskal(6, road_costs)
print("chosen edges:", tree_edges)
print("total weight:", tree_weight)

chosen edges: [(1, 2), (1, 3), (3, 4), (0, 2), (3, 5)]
total weight: 11

Five edges for six nodes, and every node is reachable. Stop Kruskal the moment forest.count drops to k instead of running it out to one component, and what you have left is single-linkage clustering into k clusters, which is the same algorithm wearing a different name.

Connected-component labelling in image processing. The standard two-pass algorithm scans the pixels once assigning provisional labels, records that two labels are equivalent whenever they meet, then resolves the equivalences and rewrites the image on a second pass. The equivalence table is a union-find. This is the machinery behind OpenCV's connectedComponents.

Graph-based image segmentation. Felzenszwalb and Huttenlocher's 2004 segmentation algorithm treats every pixel as a node, sorts the edges between neighbouring pixels by colour difference, and merges regions with a disjoint-set forest under a threshold rule. It is Kruskal with a stopping condition, and it was the segmenter underneath the selective-search region proposals used by early object detectors.

Percolation and cluster labelling in physics. The Hoshen-Kopelman algorithm labels clusters in a lattice of occupied and empty sites using union-find, and it is how percolation thresholds get estimated numerically on grids of millions of sites.

Type inference. Hindley-Milner unification, the type checker in ML, OCaml and Haskell lineages, stores type variables in a disjoint-set forest. Unifying two type variables is a union; looking up what a variable has been bound to is a find. The reason a compiler can infer types across thousands of expressions quickly is that the merge step is effectively constant.

Common mistakes

Linking the elements instead of the roots. Writing self.parent[a] = b rather than self.parent[root_a] = root_b looks like a shortcut and is a disaster. Nothing crashes and nothing loops: the root check has already established that a and b sit in different trees, so no cycle can form. What happens instead is quieter. Only a and what hangs below it move across; everything above a stays behind in the old set, and the two sets are never fully merged. Run union(0, 1), union(1, 2), union(0, 3) that way and elements 1 and 3 report different roots even though every pair was merged. Always link roots.

Forgetting to update size after linking. The line self.size[root_a] += self.size[root_b] is easy to drop, and nothing crashes. The sizes just drift away from the truth, the balancing rule starts making random choices, and you are quietly back to O(n) finds on the wrong input. Whenever find gets mysteriously slow, check this line first.

Trusting size or rank for a non-root. Once an element stops being a root, its entry is stale and meaningless. Only ever read self.size[self.find(item)].

Recursive find in Python. The two-line recursive version is the one every textbook prints, and on a chain of more than about 1,000 elements it raises RecursionError. Raising the recursion limit trades one crash for a worse one. Write the loop.

Not returning a value from union. Without the True / False, every cycle test turns into a second pair of find calls, and the component counter has to be recomputed by scanning. The return value costs nothing and carries the most useful information in the structure.

Reusing an index for two different things. Union-find is indexed by position, so if your elements are (row, column) grid cells you must flatten them consistently — row * width + column everywhere, never column * height + row in one place. This bug produces plausible-looking components that are simply wrong.

Practice

1. Add a component_size(item) method that returns how many elements share a set with item, and check it against the eight-element example above.
2. Given a node count and a list of undirected edges, return the number of connected components and the size of the largest one.
3. Detect a cycle in an undirected graph by reporting the first edge whose two endpoints already share a root, and confirm it against a graph you know has exactly one cycle.
4. Merge a list of user accounts, where each account is a name plus a list of email addresses and two accounts belong to the same person if they share any address. Map the addresses to integers first.
5. Build a rollback version: union by size, no path compression, plus an undo() that reverses the most recent merge. Explain in one sentence why path compression has to go.

Summary

Union-find answers "are these two things in the same group?" while groups keep merging, and it does it with two integers per element — a parent pointer and a subtree size. Union by size caps tree depth at log₂ n by never hanging a big tree under a small one; path compression flattens each path you walk so you never walk it twice. Neither is more than two lines, and together they buy you O(α(n)) amortised, and α(n) is at most 4 for any input that exists. Read the bound honestly, though: it is amortised, not per operation, and the structure can merge but never split.

Keep reading

• Minimum Spanning Trees — Kruskal's algorithm in full, with union-find doing the cycle test.
• Graphs in Python — how to store the edge list you feed into Kruskal, and when a matrix beats a list.
• Depth-First Search — the simpler answer when the graph is static and you only ask once.
• Big O Notation — what "amortised" actually promises, and what it does not.
• Hash Tables in Python — the dictionary you need when your elements are strings rather than indices.