Union-find (disjoint set union)

Union-find, also called disjoint set union (DSU), tells you in almost no time whether two items belong together while the items are being joined into groups, step by step. It offers two operations. find(x) names the group of x by returning one chosen member of it, the representative, and union(a, b) joins the group of a to the group of b. A group can grow, but it can never split. Inside, each group is a tree of parent pointers whose root is the representative, and two rules keep the trees short: the smaller tree goes under the larger root, and every find points the items it passes straight at the root. With both rules, any m operations on n items take O(m α(n)) time, where α, an inverse of Ackermann’s function, is at most 4 for any number of items a computer could ever store. That makes it the tool for growing networks, merging duplicates and Kruskal’s spanning trees.

Groups as trees of parent pointers

The whole structure is two arrays. parent[x] is the item one step above x in its tree, and an item that is its own parent is a root. Every group has exactly one root, so two items share a group exactly when they reach the same root. size[r] counts the items under the root r. For a million items that is two arrays of a million numbers, about 8 MB as 4-byte integers.

find(x) follows parent pointers from x until it reaches a root. union(a, b) finds both roots; if they are the same item, the two were already in one group, and otherwise one root becomes the parent of the other, which merges the trees in one step. Nothing else ever changes a pointer, so a group can grow but never split.

find and union, step by step

Eight lab computers, numbered 0 to 7, are joined by cables one at a time. After each cable the program prints the parent array and the number of groups, and it answers two questions on the way:

# Union-find with union by size and path compression, traced on eight lab computers joined by cables one at a time.
# parent[x] is x's parent in its tree; a root is its own parent and stands for its whole group. size[r] is the number
# of items in the tree of root r (it is only kept up to date for roots).


class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))   # every item starts as a group of its own
        self.size = [1] * n
        self.groups = n

    def find(self, x):
        root = x
        while self.parent[root] != root:       # walk up to the root
            root = self.parent[root]
        while self.parent[x] != root:          # path compression: point every item on the way at the root
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                       # already in one group: nothing changes
        if self.size[ra] < self.size[rb]:      # union by size: the smaller tree goes under the larger root
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        self.groups -= 1
        return True

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


uf = UnionFind(8)
print(f"{'start':<16} parent {uf.parent}  groups {uf.groups}")
steps = [("union", 0, 1), ("union", 2, 3), ("union", 1, 3), ("union", 4, 5), ("union", 6, 7), ("union", 5, 7),
         ("same", 3, 7), ("union", 1, 2), ("union", 3, 7), ("same", 0, 6)]
for op, a, b in steps:
    if op == "union":
        joined = uf.union(a, b)
        note = "" if joined else "  (already one group)"
        print(f"{f'union({a}, {b})':<16} parent {uf.parent}  groups {uf.groups}{note}")
    else:
        answer = "yes" if uf.same(a, b) else "no"
        print(f"{f'same({a}, {b})?':<16} parent {uf.parent}  {answer}")
print("sizes of the roots:", {r: uf.size[r] for r in range(8) if uf.parent[r] == r})

start            parent [0, 1, 2, 3, 4, 5, 6, 7]  groups 8
union(0, 1)      parent [0, 0, 2, 3, 4, 5, 6, 7]  groups 7
union(2, 3)      parent [0, 0, 2, 2, 4, 5, 6, 7]  groups 6
union(1, 3)      parent [0, 0, 0, 2, 4, 5, 6, 7]  groups 5
union(4, 5)      parent [0, 0, 0, 2, 4, 4, 6, 7]  groups 4
union(6, 7)      parent [0, 0, 0, 2, 4, 4, 6, 6]  groups 3
union(5, 7)      parent [0, 0, 0, 2, 4, 4, 4, 6]  groups 2
same(3, 7)?      parent [0, 0, 0, 0, 4, 4, 4, 4]  no
union(1, 2)      parent [0, 0, 0, 0, 4, 4, 4, 4]  groups 2  (already one group)
union(3, 7)      parent [0, 0, 0, 0, 0, 4, 4, 4]  groups 1
same(0, 6)?      parent [0, 0, 0, 0, 0, 4, 0, 4]  yes
sizes of the roots: {0: 8}

Each union of two separate groups lowers the count by one, from 8 to 1 over seven unions. The third cable, union(1, 3), finds the roots 0 and 2, two trees of two items, and hangs 2 under 0, so item 3 is now two steps from its root. The question same(3, 7) walks 3 → 2 → 0 and 7 → 6 → 4, answers no, and leaves parent[3] = 0 and parent[7] = 4 behind: those paths are one step long from now on. union(1, 2) changes nothing, because both items already reach root 0. The last union links root 4 under root 0, and the final question shortens the path of item 6.

Two rules that keep the trees short

Without any rule, unions can stack the trees into one long chain, and every find then walks the whole chain. The first rule decides which root goes on top. Union by size hangs the root of the smaller tree under the root of the larger one. An item then moves one level deeper only when its tree joins one at least as large, so the size of its tree at least doubles each time, and no tree is ever taller than log₂ n. Union by rank compares ranks instead of sizes, a rank being an upper bound on a tree’s height, and it caps the height just as well.

The second rule works inside find. Path compression points every item on the walk straight at the root, so the next find from any of them takes one step. Path halving points every other item at its grandparent during the same single walk, which needs no second loop.

Galler and Fischer described the structure in 1964. Tarjan proved in 1975 that union by rank with path compression runs any sequence of m operations in O(m α(m, n)) time, and Tarjan and van Leeuwen extended the bound to path halving and to union by size in 1984. A single operation can still be slower than average; the bound is for whole sequences.

Exercise and self-check

Process unions and same-group questions on up to 200,000 items and return the number of groups after each union.

def group_counts(n, operations):
    """One answer per operation: the number of groups after a union, True or False for a same-group question."""
    raise NotImplementedError("write group_counts")

import random

from groups import group_counts

LAB = [("union", 0, 1), ("union", 2, 3), ("union", 1, 3), ("union", 4, 5), ("union", 6, 7), ("union", 5, 7),
       ("same", 3, 7), ("union", 1, 2), ("union", 3, 7), ("same", 0, 6)]


def slow_counts(n, operations):
    """Recolours every item after each union: right, and far too slow for large inputs."""
    label = list(range(n))
    out = []
    for op, a, b in operations:
        if op == "union":
            old, new = label[b], label[a]
            if old != new:
                label = [new if x == old else x for x in label]
            out.append(len(set(label)))
        else:
            out.append(label[a] == label[b])
    return out


def test_lab_computers():
    """the eight lab computers of the lesson"""
    assert group_counts(8, LAB) == [7, 6, 5, 4, 3, 2, False, 2, 1, True]


def test_redundant_and_self_unions():
    """a union of one group with itself, or of an item with itself, keeps the count"""
    ops = [("union", 0, 0), ("union", 0, 1), ("union", 1, 0), ("same", 2, 2), ("same", 0, 2)]
    assert group_counts(3, ops) == [3, 2, 2, True, False]


def test_single_item():
    """one item is one group, and in the same group as itself"""
    assert group_counts(1, [("same", 0, 0), ("union", 0, 0)]) == [True, 1]


def test_random_against_recount():
    """300 random small cases, compared with a slow recount"""
    rng = random.Random(5)
    for _ in range(300):
        n = rng.randint(1, 9)
        ops = [(rng.choice(["union", "same"]), rng.randrange(n), rng.randrange(n)) for _ in range(rng.randint(0, 15))]
        assert group_counts(n, ops) == slow_counts(n, ops), (n, ops)


def test_long_chain():
    """200,000 unions that form a chain, then 200,000 questions about its far ends"""
    n = 200_000
    ops = [("union", i, i + 1) for i in range(n - 1)] + [("same", 0, i) for i in range(n - 1, -1, -1)]
    answers = group_counts(n, ops)
    assert answers[: n - 1] == list(range(n - 1, 0, -1))
    assert all(answers[n - 1:])

/** One answer per operation: the number of groups after a union, true or false for a same-group question. */
export function groupCounts(n, operations) {
  throw new Error('write groupCounts');
}

import { test, assert } from 'mysmartcopilot:test';
import { groupCounts } from './groups.mjs';

const LAB = [['union', 0, 1], ['union', 2, 3], ['union', 1, 3], ['union', 4, 5], ['union', 6, 7], ['union', 5, 7],
  ['same', 3, 7], ['union', 1, 2], ['union', 3, 7], ['same', 0, 6]];

/** Recolours every item after each union: right, and far too slow for large inputs. */
function slowCounts(n, operations) {
  let label = Array.from({ length: n }, (_, i) => i);
  const out = [];
  for (const [op, a, b] of operations) {
    if (op === 'union') {
      const oldLabel = label[b];
      const newLabel = label[a];
      if (oldLabel !== newLabel) label = label.map((x) => (x === oldLabel ? newLabel : x));
      out.push(new Set(label).size);
    } else out.push(label[a] === label[b]);
  }
  return out;
}

test('the eight lab computers of the lesson', () => {
  assert.deepEqual(groupCounts(8, LAB), [7, 6, 5, 4, 3, 2, false, 2, 1, true]);
});

test('a union of one group with itself, or of an item with itself, keeps the count', () => {
  const ops = [['union', 0, 0], ['union', 0, 1], ['union', 1, 0], ['same', 2, 2], ['same', 0, 2]];
  assert.deepEqual(groupCounts(3, ops), [3, 2, 2, true, false]);
});

test('one item is one group, and in the same group as itself', () => {
  assert.deepEqual(groupCounts(1, [['same', 0, 0], ['union', 0, 0]]), [true, 1]);
});

test('300 random small cases, compared with a slow recount', () => {
  let seed = 5;
  const random = () => (seed = (seed * 48271) % 2147483647) / 2147483647;
  const pick = (k) => Math.floor(random() * k);
  for (let t = 0; t < 300; t++) {
    const n = 1 + pick(9);
    const ops = Array.from({ length: pick(16) }, () => [random() < 0.5 ? 'union' : 'same', pick(n), pick(n)]);
    assert.deepEqual(groupCounts(n, ops), slowCounts(n, ops), JSON.stringify([n, ops]));
  }
});

test('200,000 unions that form a chain, then 200,000 questions about its far ends', () => {
  const n = 200000;
  const ops = [];
  for (let i = 0; i < n - 1; i++) ops.push(['union', i, i + 1]);
  for (let i = n - 1; i >= 0; i--) ops.push(['same', 0, i]);
  const answers = groupCounts(n, ops);
  let ok = answers.length === 2 * n - 1;
  for (let i = 0; i < n - 1 && ok; i++) if (answers[i] !== n - 1 - i) ok = false;
  for (let i = n - 1; i < answers.length && ok; i++) if (answers[i] !== true) ok = false;
  assert.ok(ok, 'the counts fall from 199,999 to 1 and every question is answered true');
});

Why it is nearly constant: the height bound proved and the steps counted Pro: opens with a Pro, Premium or Ultimate pass

Union-find in five languages, with memory measured and four bugs reproduced Pro: opens with a Pro, Premium or Ultimate pass

Loops, spanning trees, shrinking networks and a practice set Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Key takeaways

• Union-find keeps groups that only merge: find returns a group’s root and union links two roots.
• Two items share a group exactly when they have the same root; compare roots, never parents.
• Union by size (or by rank) caps the height at log₂ n; path compression makes later finds take one step.
• With both rules, m operations cost O(m α(n)), where α is at most 4 for any realistic n.