Union-Find: Disjoint Sets

in reviewThis lesson is complete and being validated before release - details may still change.

Union-find

Loading interactive demo…

The forest is the data structure: every element is a box that points at its parent, and a box that points at itself is a root, the name of its set. A find climbs to the root; a union hangs one root under another. The strips beneath are the script of pairs, the parent array, and the sizes at the roots. Tap a box to read its path.Take the tour, or press and explore. Legend:

The panel beside the stage is the real DisjointSets class from the published library executing in your browser, with the current line highlighted.

The node a find stands on, and the parent pointer it just climbed.
A root, filled; the other boxes are outlined.
The two elements the current union joins, or the question asks about.
The root just hung under another, and a union that merged two sets.
A node compression just pointed straight at its root.
A union whose two elements were one set already: in a graph, a cycle.
Operations of the script still to come.

sets counts the roots; tallest tree is the most a find can cost right now; climbs counts every parent hop taken so far, and longest find the most one find took.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

The question. Some problems never ask "what is in this set?", only "are these two things in the same set?" and "merge these two sets". Connected components of a graph, the cycle test inside Kruskal's algorithm, clusters on a grid, variables that must have the same type: in each the sets only ever grow together. A structure that answers exactly those two questions can be far simpler than a general set.

A forest of parent pointers. Give every element one number: its parent. An element that is its own parent is a root, and the root is the set's name. find(x) climbs parent pointers until it reaches a root; two elements are in the same set exactly when their finds reach the same root. union(a, b) finds both roots and, if they differ, writes one pointer: one root now points at the other. The whole structure is one array, the stage's bottom strip, and a union is one assignment into it.

Quick union and its failure. Hanging the second root under the first works, but nothing stops a tree from becoming a chain. The default script does exactly that: each union names a fresh element first, so the whole set so far hangs beneath it, and after $n - 1$ unions the find of the bottom element climbs $n - 1$ hops. A find costs $O(n)$ in the worst case, no better than a scan.

Union by size. Hang the smaller tree under the larger, and the height is bounded. Follow any element: its depth grows by one only when its tree is hung under another tree at least as large, so its tree at least doubles each time. After $k$ such events the tree holds at least $2^k$ elements, and $2^k \le n$ gives

\text{depth} \le \log_2 n .

Every find is now $O(\log n)$ . Switch the stage to by size and run the same chain script: the chain becomes a bush one level deep, because the fresh element is always the smaller tree.

Path compression. A find has just walked a path to the root. Why walk it again? Point every node on that path straight at the root. No single find gets cheaper, but the forest flattens as it is used, and the random scenario shows paths collapsing on the stage. Note what compression does not do: a node no find has visited keeps its old depth, so the tallest-tree readout can stay above one after the script ends.

The bound. Hopcroft and Ullman showed that with both tricks a sequence of $m$ operations on $n$ elements costs $O(m \log^* n)$ , where $\log^*$ counts how many times you must take a logarithm to reach one. Tarjan sharpened it to $O(m\,\alpha(n))$ : $\alpha$ is the inverse Ackermann function, which asks how many times the Ackermann function must be applied to reach $n$ , and since the Ackermann function reaches a 19,729-digit number by its fourth step, $\alpha(n) \le 4$ for anything a computer can hold. Amortized, each operation is a few hops, and Fredman and Saks proved no structure in the same model can do better.

What this structure cannot do. It never splits a set, never lists a set's members without a scan, and knows nothing about order: there is no "smallest element of the set" and no "next element". For membership plus order in logarithmic time the next lesson turns to a tree that keeps itself balanced.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

Two arrays are the whole structure. parent holds the forest and size holds a count that is only meaningful at a root; below a root the entry goes stale and is never read again. Nothing stores the members of a set.
find is a loop, not a recursion. The climb is while (parent[node] !== node), which is also the definition of a root. The climb emit sits inside that loop, so the hops the stage counts are the hops the code takes.
The mode is three questions, not three classes. bySize decides which root becomes the child; compressing decides whether find calls compress after it reaches the root. Quick union is both answers no.
Compression stops one short. The compress loop runs while a node's parent is not the root, so the node already directly under the root is left alone and the root itself never points anywhere but at itself.
union returns whether it merged. Kruskal's algorithm keeps an edge exactly when this returns true, and the same emit is the cycle detector: both finds reached one root, so nothing is written.
run is only a script runner. The published class is find, union, and connected; the stage's scenarios are data that call them in order, and the report counts hops because that is the honest measure of the work.

The forest of parent pointers was published in 1964 by Bernard Galler and Michael Fischer as a faster way for a Fortran compiler to lay out storage: EQUIVALENCE, DIMENSION, and COMMON declarations name pairs of variables that must share memory, and the compiler needs the equivalence classes. Hopcroft and Ullman bounded union by size with path compression in 1973, and in 1975 Robert Tarjan proved the exact bound: the inverse Ackermann function per operation, which never exceeds four for any input a computer can hold, yet is not constant.

1964Bernard Galler and Michael Fischer - 'An improved equivalence algorithm' in Communications of the ACM describes the disjoint-set forest, built to compute equivalence classes of Fortran variables about 40 percent faster than the published method.source
1973John Hopcroft and Jeffrey Ullman - Bound the forest with union by size and path compression by O(log* n) per operation, the iterated logarithm.source
1975Robert Tarjan - 'Efficiency of a good but not linear set union algorithm' in the Journal of the ACM proves the amortized bound is the inverse Ackermann function, and that the bound is tight.source
1989Michael Fredman and Michael Saks - Show that any disjoint-set structure in the cell-probe model must spend an inverse-Ackermann number of word accesses per operation, so the forest is optimal.source

Used today

Kruskal's minimum spanning tree - Edges are taken cheapest first and kept only when their ends are in different sets; the union-find answers that question, and the sort dominates the cost.
Connected components and cycle detection - Each edge is a union; an edge whose ends already share a root closes a cycle, and the number of roots is the number of components.
Percolation and cluster labeling - The Hoshen-Kopelman algorithm labels clusters on a grid with union and find, merging a cell's cluster with its occupied neighbours.
Unification and type inference - Type variables that must be equal are unioned; a find gives each variable its representative type.

Did you know

The structure was invented to compile Fortran: Galler and Fischer's 1964 paper computes which variables must share storage from EQUIVALENCE, DIMENSION, and COMMON declarations, and reports a 40 percent saving over the earlier published method.source
Tarjan's 1975 paper is titled 'Efficiency of a good but not linear set union algorithm': the algorithm is not linear, but its excess over linear is the inverse Ackermann function, which is below five for any practical input.source
The Ackermann function the bound inverts grows absurdly: A(4, 2) is 2 to the power 65536 minus 3, an integer with 19,729 decimal digits, which is why its inverse barely moves.source
Kruskal published his spanning tree algorithm in 1956 under a title that also names the traveling salesman problem, and Loberman and Weinberger rediscovered it the next year.source
Physicists use the structure to count clusters in percolation: the Hoshen-Kopelman algorithm of 1976 labels occupied cells on a grid by unioning each with its occupied neighbours.source

scenario

mode

seed1

sets: 1
tallest tree: 7 edges
climbs: 7 hops
longest find: 7 hops

disjoint-sets.ts

import type { Tracer } from "../trace";/** How a union chooses which root to hang under which, and whether a find flattens the path it climbed. */export const DSU_MODES = ["quick-union", "by-size", "compressed"] as const;export type DsuMode = (typeof DSU_MODES)[number];export const DSU_MIN_ELEMENTS = 2;/** Elements one forest holds at most, so a stage stays readable. */export const DSU_MAX_ELEMENTS = 16;export const DSU_MAX_UNIONS = 24;export interface DsuOptions {  /** Default compressed: union by size with path compression. */  mode?: DsuMode;}/** A pair of elements to join, in the order the script names them. */export type DsuPair = readonly [number, number];/** A run of unions followed by one connectivity question. */export interface DsuScript {  unions: readonly DsuPair[];  query: DsuPair;}export interface DsuReport {  elements: number;  /** Sets left once every union has run. */  sets: number;  unions: number;  /** Unions that joined two different sets; the rest met their own set. */  merges: number;  /** Parent hops taken by every find of the run. */  climbs: number;  hops: number;  /** The most hops one find took. */  longestFind: number;  /** The tallest tree in the forest at the end, in edges. */  height: number;  /** The script's final question. */  joined: boolean;}/** * Disjoint sets as a forest: every element points at a parent, a root * points at itself, and two elements are in the same set exactly when * they reach the same root. `find` climbs parent pointers to the root; * `union` finds both roots and hangs one under the other. Quick union * hangs the second root under the first and can grow a chain as tall * as the set, so a find costs O(n). Union by size hangs the smaller * tree under the larger: a node's tree at least doubles each time its * depth grows by one, so no tree is taller than log2 n. Path * compression points every node a find climbed straight at the root it * found, so the same walk is never paid twice. Together the two make a * sequence of m operations cost O(m alpha(n)), where alpha is the * inverse Ackermann function, at most 4 for any n a computer can hold. * * Time: O(n) per find under quick union, O(log n) by size, amortized * O(alpha(n)) with compression. Space: O(n), two arrays. */export class DisjointSets {  readonly mode: DsuMode;  /** parent[i] is i's parent, or i itself at a root. */  private readonly parent: number[];  private readonly parentOf: number[];  /** size[r] is the number of elements under root r; stale below a root. */  private readonly size: number[];  private readonly setSize: number[];  private sets: number;  private unions = 0;  private merges = 0;  private climbs = 0;  private hops = 0;  private longestFind = 0;  constructor(    readonly elements: number,    options: DsuOptions = {},    private readonly tracer?: Tracer,  ) {    if (!Number.isInteger(elements) || elements < DSU_MIN_ELEMENTS || elements > DSU_MAX_ELEMENTS) {      throw new RangeError(`elements must be in [${DSU_MIN_ELEMENTS}, ${DSU_MAX_ELEMENTS}]`);    }    this.mode = options.mode ?? "compressed";    this.parent = Array.from({ length: elements }, (_, i) => i);    this.parentOf = Array.from({ length: elements }, (_, i) => i);    this.size = Array.from({ length: elements }, () => 1);    this.setSize = Array.from({ length: elements }, () => 1);    this.sets = elements;  }  /** Whether a union hangs the smaller tree under the larger. */  get bySize(): boolean {    return this.mode !== "quick-union";  }  /** Whether a find points the nodes it climbed straight at the root. */  get compressing(): boolean {    return this.mode === "compressed";  }  /** The script in order: every union, then the final question. */  run(script: DsuScript): DsuReport {    if (script.unions.length > DSU_MAX_UNIONS) throw new RangeError(`${script.unions.length} unions exceeds ${DSU_MAX_UNIONS}`);    for (const [a, b] of script.unions) this.union(a, b);    const joined = this.connected(script.query[0], script.query[1]);    return this.report(joined);  }  /** The root of x's set: climb parent pointers until a node is its own parent. */  find(x: number): number {    this.check(x);    // ▸ start at the element and climb toward its root    this.tracer?.emit("find", { x });    let node = x;    let climbs = 0;    let hops = 0;    while (this.parent[node] !== node) {    while (this.parentOf[node] !== node) {      const next = this.parent[node]!;      const next = this.parentOf[node]!;      // ▸ one hop up a parent pointer      this.tracer?.emit("climb", { from: node, to: next });      node = next;      climbs++;      hops++;    }    this.climbs += climbs;    this.hops += hops;    this.longestFind = Math.max(this.longestFind, climbs);    this.longestFind = Math.max(this.longestFind, hops);    // ▸ a node that is its own parent is the root: the set's name    this.tracer?.emit("root", { x, root: node, climbs });    this.tracer?.emit("root", { x, root: node, hops });    if (this.compressing) this.compress(x, node);    return node;  }  /** Join the sets of a and b; false when they were one set already. */  union(a: number, b: number): boolean {    this.unions++;    const rootA = this.find(a);    const rootB = this.find(b);    if (rootA === rootB) {      // ▸ both roots are one node: the pair was already in one set      this.tracer?.emit("same", { a, b, root: rootA });      return false;    }    // Quick union hangs b's root under a's; by size, the smaller tree goes under the larger.    let child = rootB;    let parent = rootA;    let parentOf = rootA;    if (this.bySize && this.size[rootA]! < this.size[rootB]!) {    if (this.bySize && this.setSize[rootA]! < this.setSize[rootB]!) {      child = rootA;      parent = rootB;      parentOf = rootB;    }    this.parent[child] = parent;    this.parentOf[child] = parentOf;    this.size[parent] = this.size[parent]! + this.size[child]!;    this.setSize[parentOf] = this.setSize[parentOf]! + this.setSize[child]!;    this.sets--;    this.merges++;    // ▸ hang one root under the other; by size, the smaller tree goes under the larger    this.tracer?.emit("link", { child, parent, size: this.size[parent] });    this.tracer?.emit("link", { child, parentOf, setSize: this.setSize[parentOf] });    return true;  }  /** Whether a and b share a root. */  connected(a: number, b: number): boolean {    const joined = this.find(a) === this.find(b);    // ▸ two elements share a set exactly when their finds reach the same root    this.tracer?.emit("connected", { a, b, joined });    return joined;  }  /** Every element's parent, a copy. */  parents(): number[] {    return [...this.parent];    return [...this.parentOf];  }  /** Every element's size entry, a copy; meaningful at the roots. */  sizes(): number[] {    return [...this.size];    return [...this.setSize];  }  /** How many sets the forest holds. */  get count(): number {    return this.sets;  }  /** The tallest tree in the forest, in edges from its deepest node to its root. */  height(): number {    let tallest = 0;    for (let i = 0; i < this.elements; i++) {      let depth = 0;      for (let node = i; this.parent[node] !== node; node = this.parent[node]!) depth++;      for (let node = i; this.parentOf[node] !== node; node = this.parentOf[node]!) depth++;      tallest = Math.max(tallest, depth);    }    return tallest;  }  report(joined = false): DsuReport {    return {      elements: this.elements,      sets: this.sets,      unions: this.unions,      merges: this.merges,      climbs: this.climbs,      hops: this.hops,      longestFind: this.longestFind,      height: this.height(),      joined,    };  }  /** Point every node on the path from x straight at the root; the node already under the root stays. */  private compress(x: number, root: number): void {    let node = x;    while (this.parent[node] !== root) {    while (this.parentOf[node] !== root) {      const next = this.parent[node]!;      const next = this.parentOf[node]!;      this.parent[node] = root;      this.parentOf[node] = root;      // ▸ point a node the find climbed straight at the root, so the walk is never paid twice      this.tracer?.emit("compress", { x: node, from: next, to: root });      node = next;    }  }  private check(x: number): void {    if (!Number.isInteger(x) || x < 0 || x >= this.elements) throw new RangeError(`element must be in [0, ${this.elements - 1}]`);  }}

sets =: 1
climbs =: 7
height =: 7
joined =: yes

Script over in quick union mode: 7 unions left 1 set of 8 elements (7 merges), the finds took 7 hops in all and 7 hops at most, the tallest tree stands 7 edges high, and the question's answer is yes.

import type { Tracer } from "../trace";/** How a union chooses which root to hang under which, and whether a find flattens the path it climbed. */export const DSU_MODES = ["quick-union", "by-size", "compressed"] as const;export type DsuMode = (typeof DSU_MODES)[number];export const DSU_MIN_ELEMENTS = 2;/** Elements one forest holds at most, so a stage stays readable. */export const DSU_MAX_ELEMENTS = 16;export const DSU_MAX_UNIONS = 24;export interface DsuOptions { /** Default compressed: union by size with path compression. */ mode?: DsuMode;}/** A pair of elements to join, in the order the script names them. */export type DsuPair = readonly [number, number];/** A run of unions followed by one connectivity question. */export interface DsuScript { unions: readonly DsuPair[]; query: DsuPair;}export interface DsuReport { elements: number; /** Sets left once every union has run. */ sets: number; unions: number; /** Unions that joined two different sets; the rest met their own set. */ merges: number; /** Parent hops taken by every find of the run. */ climbs: number; hops: number; /** The most hops one find took. */ longestFind: number; /** The tallest tree in the forest at the end, in edges. */ height: number; /** The script's final question. */ joined: boolean;}/** * Disjoint sets as a forest: every element points at a parent, a root * points at itself, and two elements are in the same set exactly when * they reach the same root. `find` climbs parent pointers to the root; * `union` finds both roots and hangs one under the other. Quick union * hangs the second root under the first and can grow a chain as tall * as the set, so a find costs O(n). Union by size hangs the smaller * tree under the larger: a node's tree at least doubles each time its * depth grows by one, so no tree is taller than log2 n. Path * compression points every node a find climbed straight at the root it * found, so the same walk is never paid twice. Together the two make a * sequence of m operations cost O(m alpha(n)), where alpha is the * inverse Ackermann function, at most 4 for any n a computer can hold. * * Time: O(n) per find under quick union, O(log n) by size, amortized * O(alpha(n)) with compression. Space: O(n), two arrays. */export class DisjointSets { readonly mode: DsuMode; /** parent[i] is i's parent, or i itself at a root. */ private readonly parent: number[]; private readonly parentOf: number[]; /** size[r] is the number of elements under root r; stale below a root. */ private readonly size: number[]; private readonly setSize: number[]; private sets: number; private unions = 0; private merges = 0; private climbs = 0; private hops = 0; private longestFind = 0; constructor( readonly elements: number, options: DsuOptions = {}, private readonly tracer?: Tracer, ) { if (!Number.isInteger(elements) || elements < DSU_MIN_ELEMENTS || elements > DSU_MAX_ELEMENTS) { throw new RangeError(`elements must be in [${DSU_MIN_ELEMENTS}, ${DSU_MAX_ELEMENTS}]`); } this.mode = options.mode ?? "compressed"; this.parent = Array.from({ length: elements }, (_, i) => i); this.parentOf = Array.from({ length: elements }, (_, i) => i); this.size = Array.from({ length: elements }, () => 1); this.setSize = Array.from({ length: elements }, () => 1); this.sets = elements; } /** Whether a union hangs the smaller tree under the larger. */ get bySize(): boolean { return this.mode !== "quick-union"; } /** Whether a find points the nodes it climbed straight at the root. */ get compressing(): boolean { return this.mode === "compressed"; } /** The script in order: every union, then the final question. */ run(script: DsuScript): DsuReport { if (script.unions.length > DSU_MAX_UNIONS) throw new RangeError(`${script.unions.length} unions exceeds ${DSU_MAX_UNIONS}`); for (const [a, b] of script.unions) this.union(a, b); const joined = this.connected(script.query[0], script.query[1]); return this.report(joined); } /** The root of x's set: climb parent pointers until a node is its own parent. */ find(x: number): number { this.check(x); // ▸ start at the element and climb toward its root this.tracer?.emit("find", { x }); let node = x; let climbs = 0; let hops = 0; while (this.parent[node] !== node) { while (this.parentOf[node] !== node) { const next = this.parent[node]!; const next = this.parentOf[node]!; // ▸ one hop up a parent pointer this.tracer?.emit("climb", { from: node, to: next }); node = next; climbs++; hops++; } this.climbs += climbs; this.hops += hops; this.longestFind = Math.max(this.longestFind, climbs); this.longestFind = Math.max(this.longestFind, hops); // ▸ a node that is its own parent is the root: the set's name this.tracer?.emit("root", { x, root: node, climbs }); this.tracer?.emit("root", { x, root: node, hops }); if (this.compressing) this.compress(x, node); return node; } /** Join the sets of a and b; false when they were one set already. */ union(a: number, b: number): boolean { this.unions++; const rootA = this.find(a); const rootB = this.find(b); if (rootA === rootB) { // ▸ both roots are one node: the pair was already in one set this.tracer?.emit("same", { a, b, root: rootA }); return false; } // Quick union hangs b's root under a's; by size, the smaller tree goes under the larger. let child = rootB; let parent = rootA; let parentOf = rootA; if (this.bySize && this.size[rootA]! < this.size[rootB]!) { if (this.bySize && this.setSize[rootA]! < this.setSize[rootB]!) { child = rootA; parent = rootB; parentOf = rootB; } this.parent[child] = parent; this.parentOf[child] = parentOf; this.size[parent] = this.size[parent]! + this.size[child]!; this.setSize[parentOf] = this.setSize[parentOf]! + this.setSize[child]!; this.sets--; this.merges++; // ▸ hang one root under the other; by size, the smaller tree goes under the larger this.tracer?.emit("link", { child, parent, size: this.size[parent] }); this.tracer?.emit("link", { child, parentOf, setSize: this.setSize[parentOf] }); return true; } /** Whether a and b share a root. */ connected(a: number, b: number): boolean { const joined = this.find(a) === this.find(b); // ▸ two elements share a set exactly when their finds reach the same root this.tracer?.emit("connected", { a, b, joined }); return joined; } /** Every element's parent, a copy. */ parents(): number[] { return [...this.parent]; return [...this.parentOf]; } /** Every element's size entry, a copy; meaningful at the roots. */ sizes(): number[] { return [...this.size]; return [...this.setSize]; } /** How many sets the forest holds. */ get count(): number { return this.sets; } /** The tallest tree in the forest, in edges from its deepest node to its root. */ height(): number { let tallest = 0; for (let i = 0; i < this.elements; i++) { let depth = 0; for (let node = i; this.parent[node] !== node; node = this.parent[node]!) depth++; for (let node = i; this.parentOf[node] !== node; node = this.parentOf[node]!) depth++; tallest = Math.max(tallest, depth); } return tallest; } report(joined = false): DsuReport { return { elements: this.elements, sets: this.sets, unions: this.unions, merges: this.merges, climbs: this.climbs, hops: this.hops, longestFind: this.longestFind, height: this.height(), joined, }; } /** Point every node on the path from x straight at the root; the node already under the root stays. */ private compress(x: number, root: number): void { let node = x; while (this.parent[node] !== root) { while (this.parentOf[node] !== root) { const next = this.parent[node]!; const next = this.parentOf[node]!; this.parent[node] = root; this.parentOf[node] = root; // ▸ point a node the find climbed straight at the root, so the walk is never paid twice this.tracer?.emit("compress", { x: node, from: next, to: root }); node = next; } } private check(x: number): void { if (!Number.isInteger(x) || x < 0 || x >= this.elements) throw new RangeError(`element must be in [0, ${this.elements - 1}]`); }}