Union-find: the 20-line template

Union-find, also called a disjoint-set union or DSU, keeps items in groups that never overlap and answers one question quickly: are these two items in the same group? It has two operations. find(x) returns the representative of x’s group, one item that stands for the whole group, so two items are together exactly when find returns the same item for both. union(a, b) merges the group of a with the group of b. Groups only ever merge, never split, and that is why union-find suits problems in which connections arrive one at a time: friendships, cables, roads, records that share a phone number, edges of a graph. Two small rules, union by size and path halving, make a run of m operations on n items take O(m α(m, n)) time, where α is a function that stays at most 4 for any input that could ever fit in a computer.

This lesson writes the template in about 20 lines and measures what each rule saves. It shows a recursive version that runs out of stack on a long path, and it solves one problem in full: friend circles that merge as students are introduced, from the brute force to code in Python, JavaScript, Java and C++.

When union-find fits

The statement usually gives it away. Three signs point to union-find:

• The input is a list of pairs that join things: two people who met, two computers on one cable, two records with the same email address, two land cells that touch.
• The questions are about groups, not routes: whether two items are connected, how many groups there are, how large the largest one is.
• The pairs arrive over time, and the questions come in between them, or the same question is asked again and again.

Connected here means joined by a chain of pairs, in either direction. If Asha met Bilal and Bilal met Chen, all three are in one group, even though Asha never met Chen. In the language of the lesson on modelling problems as graphs, the items are the nodes of an undirected graph, the pairs are its edges, and the groups are its connected components.

A breadth-first or depth-first search over the same graph finds the same groups. The two approaches differ in what they can answer and what each change costs:

For a graph that is given in full and asked about once, both run in linear time, and a search is just as good. Two kinds of problem belong elsewhere: the fewest steps between two items is a shortest path, which breadth-first search finds, and one-way relations such as prerequisites belong to topological sort, the previous module of this track.

The forest behind the two operations

Union-find stores each group as a tree, but an unusual one. There are no child pointers: every item keeps a single number, parent[x], that points one step towards the root of its tree, and a root is the one item that is its own parent. The root is the group’s representative. find(x) follows parent pointers from x until it reaches a root. union(a, b) finds the two roots and, if they differ, makes one of them the parent of the other. That single assignment merges two whole trees: nothing below the old root moves, and every item there now reaches the new root through it.

The first panel is the array parent = [0, 0, 0, 2, 4, 4, 4, 7]. Items 0, 4 and 7 point at themselves, so there are three groups, of 4, 3 and 1 items, and find(3) walks 3, 2, 0. In the second panel, union(3, 6) found the roots 0 and 4 and put the smaller group’s root, 4, under the larger one. On the way, find(3) also pointed 3 straight at 0, which is path halving at work; the section on cost explains it. The two dashed arrows are the pointers that changed.

Every operation keeps one invariant: following parent pointers from any item ends at the root of its group. So two items are in the same group exactly when their walks end at the same root. Two more values travel with the forest. size[r] holds the number of items in the group of each root r; at an item that is no longer a root the value is out of date and never read. count holds the number of groups.

The template

Here it is in Python and JavaScript, with a short demo that builds the forest of the diagram. Either tab runs on this page:

class DSU:
    """Disjoint sets of the items 0 .. n-1: union by size, find with path halving."""

    def __init__(self, n):
        self.parent = list(range(n))  # parent[x] == x marks a root
        self.size = [1] * n           # size[r]: how many items the root r's group holds
        self.count = n                # how many groups there are

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # point x at its grandparent
            x = self.parent[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                  # one group already: nothing changes
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra               # ra is the root of the larger group
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        self.count -= 1
        return True

    def group_size(self, x):
        return self.size[self.find(x)]


if __name__ == "__main__":
    d = DSU(8)
    for a, b in [(0, 1), (2, 3), (1, 3), (4, 5), (6, 4)]:
        d.union(a, b)
    print("parent:", *d.parent)
    print("groups:", d.count, "| size of 6's group:", d.group_size(6))
    print("union(3, 6):", d.union(3, 6))
    print("parent:", *d.parent)
    print("groups:", d.count, "| size of 6's group:", d.group_size(6))
    print("union(1, 5):", d.union(1, 5), "(1 and 5 are in one group already)")

parent: 0 0 0 2 4 4 4 7
groups: 3 | size of 6's group: 3
union(3, 6): True
parent: 0 0 0 0 0 4 4 7
groups: 2 | size of 6's group: 7
union(1, 5): False (1 and 5 are in one group already)

// Disjoint sets of the items 0 .. n-1: union by size, find with path halving.
class DSU {
  constructor(n) {
    this.parent = Int32Array.from({ length: n }, (_, i) => i); // parent[x] === x: a root
    this.size = new Int32Array(n).fill(1); // size[r]: the items in root r's group
    this.count = n; // how many groups there are
  }

  find(x) {
    const parent = this.parent;
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]]; // point x at its grandparent
      x = parent[x];
    }
    return x;
  }

  union(a, b) {
    let ra = this.find(a);
    let rb = this.find(b);
    if (ra === rb) return false; // one group already: nothing changes
    if (this.size[ra] < this.size[rb]) [ra, rb] = [rb, ra]; // ra: the larger group's root
    this.parent[rb] = ra;
    this.size[ra] += this.size[rb];
    this.count -= 1;
    return true;
  }

  groupSize(x) {
    return this.size[this.find(x)];
  }
}

const d = new DSU(8);
for (const [a, b] of [[0, 1], [2, 3], [1, 3], [4, 5], [6, 4]]) d.union(a, b);
console.log("parent:", Array.from(d.parent).join(" "));
console.log("groups:", d.count, "| size of 6's group:", d.groupSize(6));
console.log("union(3, 6):", d.union(3, 6));
console.log("parent:", Array.from(d.parent).join(" "));
console.log("groups:", d.count, "| size of 6's group:", d.groupSize(6));
console.log("union(1, 5):", d.union(1, 5), "(1 and 5 are in one group already)");

parent: 0 0 0 2 4 4 4 7
groups: 3 | size of 6's group: 3
union(3, 6): true
parent: 0 0 0 0 0 4 4 7
groups: 2 | size of 6's group: 7
union(1, 5): false (1 and 5 are in one group already)

Line by line:

1. The constructor makes every item a root of its own group: parent[x] = x, size[x] = 1, and count = n.
2. find loops while x is not a root. Each pass points x at its grandparent and then moves x there. The loop never recurses, so a long path cannot exhaust the call stack.
3. union finds both roots. If they are the same, a and b are already in one group: nothing changes, and it returns False. Otherwise the root of the larger group becomes the parent of the other root, the sizes are added, count drops by one, and it returns True.
4. group_size (groupSize in JavaScript) reads the size stored at the root of x’s group.

The return value of union is often the answer itself. False means “these two were connected already”, which in a graph whose edges go both ways means the new edge closes a cycle. count falls by exactly one for every True, so after k successful unions of n items there are n − k groups.

When both groups have the same size, the template keeps the root of a’s group. Any choice is correct; the rule matters only when you trace the arrays by hand. Work out what this program prints before you read its output:

class DSU:
    def __init__(self, n):
        self.parent, self.size, self.count = list(range(n)), [1] * n, n

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

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        self.count -= 1
        return True


d = DSU(5)
print(d.union(0, 1), d.union(1, 0), d.union(2, 3), d.union(3, 1), d.count, d.find(0))

True False True True 2 2

The second call joins 1 and 0 again and returns False, and three merges leave 5 − 3 = 2 groups. In the last call both roots, 2 and 0, lead groups of two items, so 0 goes under 2 and find(0) returns 2.

In JavaScript the arrays are Int32Arrays, typed arrays of 32-bit signed integers whose contents start at 0. They hold every index and size below 2³¹. Python’s lists hold the same numbers as objects, which costs more memory and is still fine at these sizes.

Why it is fast

What each rule saves, measured

Leave both rules out and union-find still gives correct answers: link the first root under the second, and let find walk without changing anything. The program below runs four versions on three workloads and counts the parent pointers every find follows, divided by the number of operations:

"""Counts the parent pointers that find follows,
for four versions of union-find on three workloads."""
import random


def pointer_steps(n, operations, by_size, halving):
    """Runs the operations and returns how many parent pointers all the finds followed."""
    parent = list(range(n))
    size = [1] * n
    steps = 0

    def find(x):
        nonlocal steps
        while parent[x] != x:
            steps += 1
            if halving:
                parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    for op in operations:
        if op[0] == "find":
            find(op[1])
            continue
        ra, rb = find(op[1]), find(op[2])
        if ra == rb:
            continue
        if not by_size:
            parent[ra] = rb  # plain linking: the first root goes under the second
        else:
            if size[ra] < size[rb]:
                ra, rb = rb, ra
            parent[rb] = ra
            size[ra] += size[rb]
    return steps


def a_line(n):
    """0 meets 1, 1 meets 2, and so on; then item 0 is looked up n times."""
    return [("union", i, i + 1) for i in range(n - 1)] + [("find", 0)] * n


def equal_halves(n):
    """Groups merge in pairs of equal size (1+1, 2+2, 4+4, ...);
    then item n - 1 is looked up n times."""
    operations, width = [], 1
    while width < n:
        operations += [("union", i, i + width) for i in range(0, n - width, 2 * width)]
        width *= 2
    return operations + [("find", n - 1)] * n


def mixed_at_random(n):
    """2n operations, each a union or a find of random items (the same ones every run)."""
    rng = random.Random(2026)
    operations = []
    for _ in range(2 * n):
        if rng.random() < 0.5:
            operations.append(("union", rng.randrange(n), rng.randrange(n)))
        else:
            operations.append(("find", rng.randrange(n)))
    return operations


VERSIONS = [  # (name, union by size, path halving)
    ("plain", False, False),
    ("by size", True, False),
    ("halving", False, True),
    ("both", True, True),
]
WORKLOADS = [
    ("a line", a_line),
    ("equal halves", equal_halves),
    ("mixed at random", mixed_at_random),
]

print("Pointer steps per operation (an operation is one union or one find)")
print(f"{'workload':<16}{'n':>6}" + "".join(f"{name:>10}" for name, _, _ in VERSIONS))
for label, make in WORKLOADS:
    for n in (1024, 4096):
        operations = make(n)
        total = len(operations)
        cells = [pointer_steps(n, operations, s, h) / total for _, s, h in VERSIONS]
        print(f"{label:<16}{n:>6,}" + "".join(f"{c:>10,.2f}" for c in cells))

Pointer steps per operation (an operation is one union or one find)
workload             n     plain   by size   halving      both
a line           1,024    511.75      0.50      1.00      0.50
a line           4,096  2,047.75      0.50      1.00      0.50
equal halves     1,024      0.99      5.00      0.50      0.50
equal halves     4,096      1.00      6.00      0.50      0.50
mixed at random  1,024     25.66      1.25      1.39      0.78
mixed at random  4,096     74.40      1.34      1.46      0.77

• A line (0 meets 1, 1 meets 2, and so on, then item 0 is looked up n times). Plain linking turns the unions into a path through all n items, and every lookup walks the whole path: 2,047.75 pointers per operation at n = 4,096, four times as many as at 1,024. Union by size never lets the path form, and halving repairs it after a few walks.
• Equal halves (groups merge in pairs of equal size, 1 + 1, 2 + 2, 4 + 4, and then the last item is looked up n times). Here union by size on its own builds trees log₂ n levels deep, and every lookup walks all of them: 5.00 pointers per operation at 1,024 and 6.00 at 4,096, one more each time n is multiplied by four. Halving flattens the path after a handful of lookups.
• Mixed at random. Plain linking grows with n, from 25.66 to 74.40 pointers per operation; either rule alone keeps the cost between 1.25 and 1.46, and both together bring it under 0.8.

With both rules, no row of the table is above 0.78, and in every row the two rules together are the cheapest version or tied with it.

Union by size keeps every tree shallow

An item moves one level further from its root only when its root is linked under another root. Union by size links the smaller group under the larger one, or under an equal one, so each time that happens the item’s group becomes at least twice as large. A group can never hold more than n items, so this can happen at most log₂ n times. With union by size alone, no find ever follows more than ⌊log₂ n⌋ pointers: 17 for 200,000 items, 19 for 1,000,000. Union by rank, a common alternative, keeps an upper bound on each tree’s height instead of its size and gives the same guarantee; size is the more useful of the two because problems so often ask how large a group is.

Path halving shortens the paths that find walks

The fullest repair, path compression, points every item on the path straight at the root once the root is found. It needs either recursion or a second loop over the path. Path halving does a lighter repair in the single loop that find already makes: each item it visits is pointed at its grandparent, and the loop then jumps to that grandparent. Every second item on the path skips a level, and the path from where the walk started becomes about half as long:

The items that the walk skipped (5, 3 and 1 here) keep their parents, and no item ends up further from the root than it was.

Together: nearly constant time per operation

Galler and Fischer described the forest of parent pointers in 1964. Tarjan proved in 1975 that union by size together with path compression runs any sequence of m ≥ n finds mixed with up to n − 1 unions in time proportional to m α(m, n), and that some sequences really need that much. Tarjan and van Leeuwen showed in 1984 that the bound also holds with union by rank, and with path halving in place of compression: halving is one of two one-pass methods, proposed by van Leeuwen and van der Weide, that they proved as good as the best. Fredman and Saks proved in 1989 that no union-find structure, however it is built, can need fewer than about α(m, n) memory accesses per operation on average. Those bounds are amortised: they hold for the total over a whole sequence. A single find can still walk up to log₂ n pointers, but every walk shortens the paths it crosses, which makes the later finds cheaper.

α is the inverse Ackermann function. NIST’s Dictionary of Algorithms and Data Structures defines it from Ackermann’s function A, whose value grows extremely fast: α(m, n) is the smallest i ≥ 1 for which A(i, ⌊m/n⌋) is larger than log₂ n. The values come straight from that definition:

"""How slowly the inverse Ackermann function grows, worked out from its definition in
NIST's Dictionary of Algorithms and Data Structures:
    A(0, j) = j + 1,  A(i, 0) = A(i - 1, 1),  A(i, j) = A(i - 1, A(i, j - 1));
    alpha(m, n) = the smallest i >= 1 with A(i, m // n) > log2(n)."""
import math


def ackermann(i, j):
    """A(i, j) from the definition, with a stack of pending first arguments."""
    pending = [i]
    while pending:
        i = pending.pop()
        if i == 0:
            j += 1
        elif j == 0:
            pending.append(i - 1)
            j = 1
        else:
            pending += [i - 1, i]  # A(i - 1, A(i, j - 1)): work out A(i, j - 1) first
            j -= 1
    return j


# The definition, run for small arguments, matches these closed forms,
# which then give the values that are too big to run.
CLOSED = {1: lambda j: j + 2, 2: lambda j: 2 * j + 3, 3: lambda j: 2 ** (j + 3) - 3}
for i, form in CLOSED.items():
    assert all(ackermann(i, j) == form(j) for j in range(6)), i
a = {i: form(1) for i, form in CLOSED.items()}
a[4] = CLOSED[3](CLOSED[3](1))  # A(4, 1) = A(3, A(4, 0)) and A(4, 0) = A(3, 1)
for i in range(1, 5):
    print(f"A({i}, 1) = {a[i]:,}")


def alpha(n):
    """alpha(m, n) with m = n, so m // n = 1; A(i, 1) > log2(n) means 2 ** A(i, 1) > n."""
    return next(i for i in range(1, 5) if 2 ** a[i] > n)


SIZES = [("7", 7), ("8", 8), ("31", 31), ("32", 32), ("8,191", 8_191), ("8,192", 8_192),
         ("10**6", 10**6), ("10**18", 10**18), ("10**80", 10**80)]
for label, n in SIZES:
    print(f"alpha(n, n) for n = {label}: {alpha(n)}")
digits = math.floor(65533 * math.log10(2)) + 1
print("With m >= n, alpha(m, n) is at most 4 for every n below 2 ** 65,533,")
print(f"a number of {digits:,} digits")

A(1, 1) = 3
A(2, 1) = 5
A(3, 1) = 13
A(4, 1) = 65,533
alpha(n, n) for n = 7: 1
alpha(n, n) for n = 8: 2
alpha(n, n) for n = 31: 2
alpha(n, n) for n = 32: 3
alpha(n, n) for n = 8,191: 3
alpha(n, n) for n = 8,192: 4
alpha(n, n) for n = 10**6: 4
alpha(n, n) for n = 10**18: 4
alpha(n, n) for n = 10**80: 4
With m >= n, alpha(m, n) is at most 4 for every n below 2 ** 65,533,
a number of 19,728 digits

With as many operations as items, α reaches 4 at n = 8,192 and stays 4 for every n below 2 to the power 65,533, so for any input a computer could hold it is a small constant. In practice that means a few pointer steps per operation, and the worked problem below measures about one.

A problem solved in full: friend circles as students meet

Three examples, which every version of the code below runs:

1. n = 6 with the introductions (0, 1), (2, 3), (1, 2), (4, 5), (3, 0), (5, 5) gives (5, 2), (4, 2), (3, 4), (2, 4), (2, 4), (2, 4). The third introduction merges two circles of two into one of four; the fifth joins two students who are already in one circle, and the sixth names one student twice.
2. n = 1 with the introduction (0, 0) gives (1, 1).
3. n = 5 with (3, 4), (4, 3), (0, 4), (1, 2), (2, 3) gives (4, 2), (4, 2), (3, 3), (2, 3), (1, 5): the repeated pair changes nothing, and the last introduction brings everyone together.

The brute force: recount every circle after each introduction

Keep every introduction in adjacency lists, and after each new one, run a breadth-first search from every student not yet reached, counting the circles and their sizes. It is plainly correct, which makes it the reference for testing a faster version. Its cost is the problem: after introduction i the search visits all n students and all 2i list entries, so the total is m·n + m(m + 1), about 8 × 10¹⁰ at the limits. At the rough budgets of the lesson on constraints, ten million simple operations a second in CPython and a hundred million in C++, that is more than two hours of Python and more than ten minutes of C++.

What to notice

Introductions only ever merge circles; nothing ever splits one. And the questions ask for counts and sizes, never for the chain of introductions that links two students. Merging groups and remembering their sizes is exactly what union-find does, so the circles can be kept up to date in place of being recounted.

Union-find, step by step

1. Make a union-find of the n students: count starts at n, and largest starts at 1.
2. For each introduction (a, b), call union(a, b).
3. If it returns True, two circles merged, and the new one is the only circle that can be larger than before: largest = max(largest, group_size(a)).
4. Record (count, largest).

Why it is correct

The loop keeps one invariant: after i introductions, the groups of the union-find are exactly the circles of those i introductions, count is how many there are, and largest is the size of the biggest.

1. Initialisation. Before any introduction every student is a circle of one, and the union-find starts with n groups of one, count = n and largest = 1.
2. Maintenance. Introduction (a, b) links every student of a’s circle to every student of b’s circle and changes no other circle. If the two circles are different, union merges exactly those two groups and lowers count by one. If they are the same circle, union returns False and nothing changes, as nothing should. Circles never shrink, so the largest circle is either the old largest or the one just made, which is what step 3 keeps.
3. Termination. Every recorded pair is right at the moment it is recorded, so all m answers are right.

A dry run

The first example, one row per introduction. roots shows what the two finds returned, and the arrays are shown after the introduction:

"""The first example traced: one row per introduction, with the roots that find returned
and the arrays after the introduction."""
n = 6
introductions = [(0, 1), (2, 3), (1, 2), (4, 5), (3, 0), (5, 5)]
parent = list(range(n))
size = [1] * n
count, largest = n, 1


def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x


WIDTHS = [7, 7, 8, 13, 21, 9, 0]  # one width per column; the last column is not padded


def row(*cells):
    print("".join(f"{cell:<{width}}" for cell, width in zip(cells, WIDTHS)).rstrip())


row("meets", "roots", "merged", "parent", "sizes at roots", "circles", "largest")
for a, b in introductions:
    ra, rb = find(a), find(b)
    roots = f"{ra},{rb}"
    merged = ra != rb
    if merged:
        if size[ra] < size[rb]:
            ra, rb = rb, ra
        parent[rb] = ra
        size[ra] += size[rb]
        count -= 1
        largest = max(largest, size[ra])
    at_roots = " ".join(f"{r}:{size[r]}" for r in range(n) if parent[r] == r)
    row(f"{a}-{b}", roots, "yes" if merged else "no", " ".join(map(str, parent)), at_roots,
        count, largest)

meets  roots  merged  parent       sizes at roots       circles  largest
0-1    0,1    yes     0 0 2 3 4 5  0:2 2:1 3:1 4:1 5:1  5        2
2-3    2,3    yes     0 0 2 2 4 5  0:2 2:2 4:1 5:1      4        2
1-2    0,2    yes     0 0 0 2 4 5  0:4 4:1 5:1          3        4
4-5    4,5    yes     0 0 0 2 4 4  0:4 4:2              2        4
3-0    0,0    no      0 0 0 0 4 4  0:4 4:2              2        4
5-5    4,4    no      0 0 0 0 4 4  0:4 4:2              2        4

Introduction 1-2 is the first to meet two roots, 0 and 2, that each lead two students, so the tie keeps 0, and 2 goes under it. In row 3-0, find(3) walks 3, 2, 0 and points 3 at its grandparent 0 on the way, which is why the parent array changes although no circle does. The last row names student 5 twice: both finds return 4, and nothing merges.

The code in four languages

Four versions of one solution. Press Run on the Python or the JavaScript tab to try it on this page:

class DSU:
    """The lesson's template: union by size, find with path halving."""

    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.count = n

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

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        self.count -= 1
        return True


def circles_after_each(n, introductions):
    """After each introduction: (how many circles there are,
    how many students the largest one has)."""
    dsu = DSU(n)
    largest = 1
    answers = []
    for a, b in introductions:
        if dsu.union(a, b):
            largest = max(largest, dsu.size[dsu.find(a)])
        answers.append((dsu.count, largest))
    return answers


EXAMPLES = [
    (6, [(0, 1), (2, 3), (1, 2), (4, 5), (3, 0), (5, 5)]),
    (1, [(0, 0)]),
    (5, [(3, 4), (4, 3), (0, 4), (1, 2), (2, 3)]),
]
for n, introductions in EXAMPLES:
    answers = circles_after_each(n, introductions)
    print(f"n = {n}:", " ".join(f"({c}, {big})" for c, big in answers))

n = 6: (5, 2) (4, 2) (3, 4) (2, 4) (2, 4) (2, 4)
n = 1: (1, 1)
n = 5: (4, 2) (4, 2) (3, 3) (2, 3) (1, 5)

// The lesson's template: union by size, find with path halving.
class DSU {
  constructor(n) {
    this.parent = Int32Array.from({ length: n }, (_, i) => i);
    this.size = new Int32Array(n).fill(1);
    this.count = n;
  }

  find(x) {
    const parent = this.parent;
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]];
      x = parent[x];
    }
    return x;
  }

  union(a, b) {
    let ra = this.find(a);
    let rb = this.find(b);
    if (ra === rb) return false;
    if (this.size[ra] < this.size[rb]) [ra, rb] = [rb, ra];
    this.parent[rb] = ra;
    this.size[ra] += this.size[rb];
    this.count -= 1;
    return true;
  }
}

// After each introduction: [how many circles there are,
// how many students the largest one has].
function circlesAfterEach(n, introductions) {
  const dsu = new DSU(n);
  let largest = 1;
  const answers = [];
  for (const [a, b] of introductions) {
    if (dsu.union(a, b)) largest = Math.max(largest, dsu.size[dsu.find(a)]);
    answers.push([dsu.count, largest]);
  }
  return answers;
}

const EXAMPLES = [
  [6, [[0, 1], [2, 3], [1, 2], [4, 5], [3, 0], [5, 5]]],
  [1, [[0, 0]]],
  [5, [[3, 4], [4, 3], [0, 4], [1, 2], [2, 3]]],
];
for (const [n, introductions] of EXAMPLES) {
  const answers = circlesAfterEach(n, introductions);
  console.log(`n = ${n}:`, answers.map(([c, big]) => `(${c}, ${big})`).join(" "));
}

n = 6: (5, 2) (4, 2) (3, 4) (2, 4) (2, 4) (2, 4)
n = 1: (1, 1)
n = 5: (4, 2) (4, 2) (3, 3) (2, 3) (1, 5)

import java.util.ArrayList;
import java.util.List;

public class Circles {
    /** The lesson's template: union by size, find with path halving. */
    static final class DSU {
        final int[] parent;
        final int[] size;
        int count;

        DSU(int n) {
            parent = new int[n];
            size = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
            count = n;
        }

        int find(int x) {
            while (parent[x] != x) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }

        boolean union(int a, int b) {
            int ra = find(a), rb = find(b);
            if (ra == rb) return false;
            if (size[ra] < size[rb]) {
                int t = ra;
                ra = rb;
                rb = t;
            }
            parent[rb] = ra;
            size[ra] += size[rb];
            count--;
            return true;
        }
    }

    /** After each introduction: {how many circles, how many students in the largest}. */
    static List<int[]> circlesAfterEach(int n, int[][] introductions) {
        DSU dsu = new DSU(n);
        int largest = 1;
        List<int[]> answers = new ArrayList<>();
        for (int[] pair : introductions) {
            if (dsu.union(pair[0], pair[1])) {
                largest = Math.max(largest, dsu.size[dsu.find(pair[0])]);
            }
            answers.add(new int[] {dsu.count, largest});
        }
        return answers;
    }

    public static void main(String[] args) {
        int[] sizes = {6, 1, 5};
        int[][][] examples = {
            {{0, 1}, {2, 3}, {1, 2}, {4, 5}, {3, 0}, {5, 5}},
            {{0, 0}},
            {{3, 4}, {4, 3}, {0, 4}, {1, 2}, {2, 3}},
        };
        for (int e = 0; e < sizes.length; e++) {
            StringBuilder line = new StringBuilder("n = " + sizes[e] + ":");
            for (int[] answer : circlesAfterEach(sizes[e], examples[e])) {
                line.append(" (").append(answer[0]).append(", ").append(answer[1]);
                line.append(")");
            }
            System.out.println(line);
        }
    }
}

#include <algorithm>
#include <numeric>
#include <print>
#include <utility>
#include <vector>

// The lesson's template: union by size, find with path halving.
// "union" is a keyword in C++, so the merge is called unite().
struct DSU {
    std::vector<int> parent, size;
    int count;

    explicit DSU(int n) : parent(n), size(n, 1), count(n) {
        std::iota(parent.begin(), parent.end(), 0);
    }

    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    bool unite(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;
        if (size[ra] < size[rb]) std::swap(ra, rb);
        parent[rb] = ra;
        size[ra] += size[rb];
        --count;
        return true;
    }
};

using Pairs = std::vector<std::pair<int, int>>;

// After each introduction: {how many circles there are,
// how many students the largest one has}.
Pairs circles_after_each(int n, const Pairs& introductions) {
    DSU dsu(n);
    int largest = 1;
    Pairs answers;
    for (auto [a, b] : introductions) {
        if (dsu.unite(a, b)) largest = std::max(largest, dsu.size[dsu.find(a)]);
        answers.emplace_back(dsu.count, largest);
    }
    return answers;
}

int main() {
    const std::vector<std::pair<int, Pairs>> examples = {
        {6, {{0, 1}, {2, 3}, {1, 2}, {4, 5}, {3, 0}, {5, 5}}},
        {1, {{0, 0}}},
        {5, {{3, 4}, {4, 3}, {0, 4}, {1, 2}, {2, 3}}},
    };
    for (const auto& [n, introductions] : examples) {
        std::print("n = {}:", n);
        for (auto [circles, largest] : circles_after_each(n, introductions)) {
            std::print(" ({}, {})", circles, largest);
        }
        std::println();
    }
}

Java and C++ need a compiler, so their output comes from a terminal session:

from session import run, versions

# Circles.java runs as a single source file;
# circles.cpp is built with the sanitizers on, then run.
versions("java -version", "clang++ --version")
run("""
java Circles.java
clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined circles.cpp -o circles
./circles
""")

# openjdk version "27"
# Apple clang version 21.0.0 (clang-2100.3.34.2)
$ java Circles.java
n = 6: (5, 2) (4, 2) (3, 4) (2, 4) (2, 4) (2, 4)
n = 1: (1, 1)
n = 5: (4, 2) (4, 2) (3, 3) (2, 3) (1, 5)
$ clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined circles.cpp -o circles
$ ./circles
n = 6: (5, 2) (4, 2) (3, 4) (2, 4) (2, 4) (2, 4)
n = 1: (1, 1)
n = 5: (4, 2) (4, 2) (3, 3) (2, 3) (1, 5)

All four print the same three lines. A few details differ between the languages:

• C++ reserves the word union (it declares a kind of class that holds one of several members at a time), so the method is called unite. Java, JavaScript and Python have no such keyword.
• Java runs a program kept in a single source file with java Circles.java, compiling it in memory first, which the java launcher has done since Java 11 (JEP 330).
• The C++ build turns on AddressSanitizer and UndefinedBehaviorSanitizer, two Clang checkers that stop a program at a bad memory access or at undefined behaviour; here they found nothing to report.
• The sizes reach at most 200,000, so 32-bit integers are enough everywhere. A problem that adds sizes up, such as the exercise below, needs 64 bits in Java and C++.

Checked against the brute force

"""Union-find checked against a BFS recount after every introduction,
then the work of both counted."""
import random
from collections import deque


def circles_union_find(n, introductions):
    """The lesson's solution; also returns how many parent pointers its finds followed."""
    parent, size = list(range(n)), [1] * n
    count, largest, steps = n, 1, 0
    answers = []

    def find(x):
        nonlocal steps
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
            steps += 1
        return x

    for a, b in introductions:
        ra, rb = find(a), find(b)
        if ra != rb:
            if size[ra] < size[rb]:
                ra, rb = rb, ra
            parent[rb] = ra
            size[ra] += size[rb]
            count -= 1
            largest = max(largest, size[ra])
        answers.append((count, largest))
    return answers, steps


def circles_brute_force(n, introductions):
    """Recounts every circle with BFS after each introduction.

    It also returns its work: the students and list entries that its searches visited."""
    friends = [[] for _ in range(n)]
    answers, work = [], 0
    for a, b in introductions:
        friends[a].append(b)
        friends[b].append(a)
        seen = [False] * n
        sizes = []
        for start in range(n):
            if seen[start]:
                continue
            seen[start] = True
            queue, members = deque([start]), 0
            while queue:
                person = queue.popleft()
                members += 1
                work += 1 + len(friends[person])
                for other in friends[person]:
                    if not seen[other]:
                        seen[other] = True
                        queue.append(other)
            sizes.append(members)
        answers.append((len(sizes), max(sizes)))
    return answers, work


def random_pairs(n, m):
    return [(rng.randrange(n), rng.randrange(n)) for _ in range(m)]


rng = random.Random(7)
cases = 2000
for _ in range(cases):
    n = rng.randint(1, 9)
    introductions = random_pairs(n, rng.randint(1, 14))
    fast = circles_union_find(n, introductions)[0]
    assert fast == circles_brute_force(n, introductions)[0], (n, introductions)
print(f"{cases:,} random cases with 1 to 9 students: both give the same answers")

n = m = 1000
introductions = random_pairs(n, m)
answers, work = circles_brute_force(n, introductions)
assert answers == circles_union_find(n, introductions)[0]
print(f"n = m = {n:,}: the BFS recounts visited {work:,} students and list entries")
print(f"n = m = {n:,}: m*n + m*(m + 1) = {m * n + m * (m + 1):,}")

n = m = 200_000
introductions = random_pairs(n, m)
answers, steps = circles_union_find(n, introductions)
visits = m * n + m * (m + 1)
print(f"n = m = {n:,}: the BFS recounts would visit m*n + m*(m + 1) = {visits:,}")
print(f"n = m = {n:,}: union-find's finds followed {steps:,} parent pointers in all")
circles, largest = answers[-1]
print(f"after the last introduction: {circles:,} circles, the largest of {largest:,}")

2,000 random cases with 1 to 9 students: both give the same answers
n = m = 1,000: the BFS recounts visited 2,001,000 students and list entries
n = m = 1,000: m*n + m*(m + 1) = 2,001,000
n = m = 200,000: the BFS recounts would visit m*n + m*(m + 1) = 80,000,200,000
n = m = 200,000: union-find's finds followed 206,204 parent pointers in all
after the last introduction: 32,452 circles, the largest of 159,297

The random cases are tiny and full of repeated pairs and students introduced to themselves, so every special case comes up hundreds of times. With 1,000 students and 1,000 introductions, the program counts what the brute force visits and gets exactly m·n + m(m + 1); at the limits, 200,000 of each, that formula gives 80,000,200,000 visits. Union-find’s finds followed 206,204 parent pointers for the same size, about one per introduction.

The cost

The union-find version needs two arrays of n numbers and keeps none of the introductions; the brute force must keep every one of them in its adjacency lists.

A recursive find that runs out of stack

Full path compression is often written recursively: if x is not a root, set its parent to find of its parent, then return that parent. It is correct and fits in two lines, but it needs one call frame for every item on the path. Union by size keeps paths at most log₂ n long, so the recursion stays shallow. The danger comes when the paths are long, for example when the links go in without union by size, or when the parent array is given as the input. Here is the line that plain linking builds from union(0, 1), union(1, 2) and so on, 100,000 items long:

"""A recursive find on a line of 100,000 items, then the loop with path halving on it."""
import sys

N = 100_000
# The parent array that plain linking builds from union(0, 1), union(1, 2), ...:
# 0 -> 1 -> 2 -> ... -> 99999.
parent = list(range(1, N)) + [N - 1]


def find_recursive(x):
    """Full path compression, the short recursive way."""
    if parent[x] != x:
        parent[x] = find_recursive(parent[x])
    return parent[x]


def find_halving(x):
    """The template's loop: no recursion; every other item on the path skips a level."""
    while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x


def depth(x):
    """How many pointers lead from x to its root."""
    d = 0
    while parent[x] != x:
        x = parent[x]
        d += 1
    return d


print("recursion limit:", sys.getrecursionlimit())
try:
    find_recursive(0)
except RecursionError as error:
    print("recursive find(0) stopped with RecursionError:", error)
print(f"depth of item 0: {depth(0):,} (the line is unchanged)")

calls = 0
while depth(0) > 1:
    root = find_halving(0)
    calls += 1
    if calls <= 4 or depth(0) == 1:
        print(f"after call {calls} of find(0): root {root:,}, depth of item 0: {depth(0):,}")
print("calls until item 0 points straight at the root:", calls)

recursion limit: 1000
recursive find(0) stopped with RecursionError: maximum recursion depth exceeded
depth of item 0: 99,999 (the line is unchanged)
after call 1 of find(0): root 99,999, depth of item 0: 50,000
after call 2 of find(0): root 99,999, depth of item 0: 25,000
after call 3 of find(0): root 99,999, depth of item 0: 12,500
after call 4 of find(0): root 99,999, depth of item 0: 6,250
after call 17 of find(0): root 99,999, depth of item 0: 1
calls until item 0 points straight at the root: 17

// A recursive find on a line of 100,000 items, then the loop with path halving on it.
const N = 100_000;
// The parent array that plain linking builds from union(0, 1), union(1, 2), ...:
// 0 -> 1 -> 2 -> ... -> 99999.
const parent = Int32Array.from({ length: N }, (_, i) => Math.min(i + 1, N - 1));

function findRecursive(x) {
  if (parent[x] !== x) parent[x] = findRecursive(parent[x]); // full path compression
  return parent[x];
}

function findHalving(x) {
  while (parent[x] !== x) {
    parent[x] = parent[parent[x]];
    x = parent[x];
  }
  return x;
}

function depth(x) {
  let d = 0;
  while (parent[x] !== x) {
    x = parent[x];
    d += 1;
  }
  return d;
}

try {
  findRecursive(0);
} catch (error) {
  console.log(`recursive find(0) stopped with ${error.name}: ${error.message}`);
}
console.log(`depth of item 0: ${depth(0).toLocaleString("en")} (the line is unchanged)`);

let calls = 0;
while (depth(0) > 1) {
  findHalving(0);
  calls += 1;
}
console.log("calls of the halving find until item 0 points straight at the root:", calls);

recursive find(0) stopped with RangeError: Maximum call stack size exceeded
depth of item 0: 99,999 (the line is unchanged)
calls of the halving find until item 0 points straight at the root: 17

CPython stops the first find(0) at its recursion limit, 1,000 frames by default, with RecursionError. The limit can be raised with sys.setrecursionlimit(), but the Python documentation warns that a limit set too high can crash the interpreter. Node.js gives up too, with RangeError: Maximum call stack size exceeded, the message MDN lists for Chrome and Safari, and Java throws StackOverflowError when an application recurses too deeply. In both runs the error came before any pointer had changed, because the assignments happen only as the calls return, so the line was still whole afterwards.

The halving loop needs no call stack at all. Its first walk halves the depth of item 0, from 99,999 to 50,000, and each later walk halves it again: 17 calls bring item 0 next to the root. Prefer the loop in every language, even with union by size, so that the template is safe whatever builds the trees.

Variants of the template

• Labels that are not 0 to n − 1. Give each name, email address or coordinate a number the first time it is seen, with a dictionary, and run the template on the numbers. A grid cell (r, c) can use the number r · cols + c.
• Items that arrive later. Append a new item to both arrays (parent gets its own index, size gets 1) and add one to count.
• Full path compression with two loops. Find the root first, then walk the path again and point every item on it at the root. It has the same bound as halving and takes two passes.
• What the rest of this module builds on it. The first union that returns False finds the cable that closed a loop; records are merged through the identifiers they share; a weight stored on each parent pointer answers ratio and parity questions; and queries sorted by a limit are answered offline as edges are added in order.

Exercise

reachable_pairs(5, [(0, 1), (1, 2), (3, 4), (2, 0), (2, 3)])   # [1, 3, 4, 4, 10]

def reachable_pairs(n, roads):
    """After each road, how many pairs of different towns can reach each other. One number per road."""
    # Replace this line with your code.
    return []

import random
from collections import deque

from pairs import reachable_pairs


def trusted(n, roads):
    """The answer the tests trust: after each road, BFS finds every group, and a group of s towns has s(s-1)/2 pairs."""
    neighbours = [[] for _ in range(n)]
    answers = []
    for a, b in roads:
        neighbours[a].append(b)
        neighbours[b].append(a)
        seen = [False] * n
        pairs = 0
        for start in range(n):
            if seen[start]:
                continue
            seen[start] = True
            queue, towns = deque([start]), 0
            while queue:
                town = queue.popleft()
                towns += 1
                for other in neighbours[town]:
                    if not seen[other]:
                        seen[other] = True
                        queue.append(other)
            pairs += towns * (towns - 1) // 2
        answers.append(pairs)
    return answers


def test_example():
    """the example of the prompt: 1, 3, 4, 4, 10"""
    assert reachable_pairs(5, [(0, 1), (1, 2), (3, 4), (2, 0), (2, 3)]) == [1, 3, 4, 4, 10]


def test_no_roads():
    """no roads, no numbers"""
    assert reachable_pairs(4, []) == []


def test_road_to_itself_and_repeated_roads():
    """a road from a town to itself joins nothing, and a repeated road adds no pair"""
    assert reachable_pairs(3, [(1, 1), (0, 2), (2, 0), (0, 2)]) == [0, 1, 1, 1]
    assert reachable_pairs(1, [(0, 0)]) == [0]


def test_two_groups_merge():
    """groups of 3 and 4 towns that meet add 3 * 4 = 12 pairs at once"""
    roads = [(0, 1), (1, 2), (3, 4), (4, 5), (5, 6), (2, 6)]
    assert reachable_pairs(7, roads) == [1, 3, 4, 6, 9, 21]


def test_a_long_line_then_its_two_ends():
    """200,000 towns joined in a line, then its two ends joined again: answers beyond 32 bits, and a long path"""
    n = 200_000
    answers = reachable_pairs(n, [(i, i + 1) for i in range(n - 1)] + [(0, n - 1)])
    assert answers[:3] == [1, 3, 6]
    assert answers[-2] == answers[-1] == n * (n - 1) // 2 == 19_999_900_000


def test_hub_roads_stay_fast():
    """200,000 roads from town 0 to every other town, in an order that makes plain linking quadratic"""
    n = 200_000
    answers = reachable_pairs(n, [(0, i) for i in range(1, n)] + [(i, 0) for i in range(1, n)])
    assert answers[n - 2] == n * (n - 1) // 2
    assert answers[-1] == answers[n - 2]


def test_random_against_bfs():
    """400 random cases of up to 10 towns, checked against a BFS recount after every road"""
    rng = random.Random(22)
    for _ in range(400):
        n = rng.randint(1, 10)
        roads = [(rng.randrange(n), rng.randrange(n)) for _ in range(rng.randint(0, 15))]
        assert reachable_pairs(n, roads) == trusted(n, roads), (n, roads)

/**
 * After each road, how many pairs of different towns can reach each other. Returns one number per road.
 * Towns are numbered 0 to n - 1; each road is a pair [a, b] and can be used both ways.
 */
export function reachablePairs(n, roads) {
  // Replace this line with your code.
  return [];
}

import { test, assert } from 'mysmartcopilot:test';
import { reachablePairs } from './pairs.mjs';

let seed = 22;
const random = () => (seed = (seed * 48271) % 2147483647) / 2147483647;
const randInt = (lo, hi) => lo + Math.floor(random() * (hi - lo + 1));

// The answer the tests trust: after each road, BFS finds every group, and a group of s towns has s(s-1)/2 pairs.
function trusted(n, roads) {
  const neighbours = Array.from({ length: n }, () => []);
  const answers = [];
  for (const [a, b] of roads) {
    neighbours[a].push(b);
    neighbours[b].push(a);
    const seen = new Array(n).fill(false);
    let pairs = 0;
    for (let start = 0; start < n; start++) {
      if (seen[start]) continue;
      seen[start] = true;
      const queue = [start];
      for (let head = 0; head < queue.length; head++) {
        for (const other of neighbours[queue[head]]) {
          if (!seen[other]) {
            seen[other] = true;
            queue.push(other);
          }
        }
      }
      pairs += (queue.length * (queue.length - 1)) / 2;
    }
    answers.push(pairs);
  }
  return answers;
}

test('the example of the prompt: 1, 3, 4, 4, 10', () => {
  assert.deepEqual(reachablePairs(5, [[0, 1], [1, 2], [3, 4], [2, 0], [2, 3]]), [1, 3, 4, 4, 10]);
});

test('no roads, no numbers', () => {
  assert.deepEqual(reachablePairs(4, []), []);
});

test('a road from a town to itself joins nothing, and a repeated road adds no pair', () => {
  assert.deepEqual(reachablePairs(3, [[1, 1], [0, 2], [2, 0], [0, 2]]), [0, 1, 1, 1]);
  assert.deepEqual(reachablePairs(1, [[0, 0]]), [0]);
});

test('groups of 3 and 4 towns that meet add 3 * 4 = 12 pairs at once', () => {
  assert.deepEqual(reachablePairs(7, [[0, 1], [1, 2], [3, 4], [4, 5], [5, 6], [2, 6]]), [1, 3, 4, 6, 9, 21]);
});

test('100,000 towns joined in a line, then its two ends joined again', () => {
  const n = 100000;
  const roads = Array.from({ length: n - 1 }, (_, i) => [i, i + 1]);
  roads.push([0, n - 1]);
  const answers = reachablePairs(n, roads);
  assert.deepEqual(answers.slice(0, 3), [1, 3, 6]);
  assert.equal(answers[n - 2], 4999950000);
  assert.equal(answers[n - 1], 4999950000);
});

test('100,000 roads from town 0 to every other town, then the same roads the other way', () => {
  const n = 100000;
  const roads = Array.from({ length: n - 1 }, (_, i) => [0, i + 1]);
  for (let i = 1; i < n; i++) roads.push([i, 0]);
  const answers = reachablePairs(n, roads);
  assert.equal(answers[n - 2], 4999950000);
  assert.equal(answers[answers.length - 1], 4999950000);
});

test('400 random cases of up to 10 towns, checked against a BFS recount after every road', () => {
  for (let trial = 0; trial < 400; trial++) {
    const n = randInt(1, 10);
    const roads = Array.from({ length: randInt(0, 15) }, () => [randInt(0, n - 1), randInt(0, n - 1)]);
    assert.deepEqual(reachablePairs(n, roads), trusted(n, roads), JSON.stringify([n, roads]));
  }
});

Interview questions

Fresher · What do find and union return in a union-find, and what does it mean when union returns False?

find(x) returns the root of x’s group: the item reached by following parent pointers from x until one points at itself. The root stands for the whole group, so two items are in the same group exactly when find returns the same root for both. union(a, b) finds both roots. If they are the same, a and b were already in one group, nothing changes, and it returns False; otherwise it links the root of the smaller group under the root of the larger, adds the sizes, lowers the group count by one and returns True. False carries information of its own: in a graph whose edges go both ways, a union that returns False means that the new edge joins two items that were already connected, so it closes a cycle.

Fresher to 2–5 years · Why does union by size keep every tree of a union-find at most log₂ n levels deep?

An item gets one level further from its root only when the root of its group is linked under another root. Union by size always links the smaller group under the larger one, or under one of equal size, so every time an item’s depth grows by one, the group it belongs to at least doubles. A group can never hold more than n items, and doubling from 1 item reaches n after log₂ n doublings, so no item is ever more than ⌊log₂ n⌋ pointers from its root: 17 for 200,000 items. That bound holds even with no path compression at all, and it is also why a recursive find is safe once union by size is in place.

Key takeaways

• Union-find keeps groups that only merge. find(x) returns the root of x’s group, and union(a, b) links one root under the other and returns whether anything merged.
• The template is two arrays and a count: parent (a root is its own parent), size (read only at roots) and count (one less after every merge).
• Union by size keeps every tree within ⌊log₂ n⌋ levels; path halving points each visited item at its grandparent. Together they make m operations take O(m α(m, n)) time, and α(n, n) is at most 4 for any realistic n.
• Measured: plain linking walked 2,047.75 pointers per operation on a line of 4,096 items, union by size alone 6.00 on equal halves, and both rules together at most 0.78 in every workload.
• Choose union-find for “same group?”, “how many groups?” and “how large?” while connections only arrive. Choose a search for paths, distances, one-way edges or connections that are removed.
• Write find as a loop. A recursive find with plain linking stopped with RecursionError in Python and RangeError in Node.js on a line of 100,000 items.