Data Structures for Disjoint Sets (Union-Find)

By the end you will be able to implement and trace makeSet, UNION and findSet under two representations (linked lists with the weighted-union heuristic, and rooted forests with union by rank and path compression), use them to solve connectedComponents on a graph that arrives edge-by-edge, and understand — visually, not via the full proof — why a sequence of disjoint-set operations with both forest heuristics runs in essentially linear time, governed by the almost-constant inverse-Ackermann function α(n).

1. Disjoint-set operations: make set, UNION, find set

A disjoint-set data structure maintains a collection S = {S₁, …, Sₖ} of dynamic sets. Each set has a representative — some member of the set, chosen however the data structure likes, but it must stay consistent: asking findSet twice on two elements of the same (unmodified) set must return the same representative both times. The sets are disjoint: every element belongs to exactly one set at a time.

• makeSet(x) — creates a new set whose only member is x (so x must not already be in another set).
• union(x, y) — merges the set containing x with the set containing y into one new set, destroying the two originals conceptually (some representative of the union becomes the new representative).
• findSet(x) — returns a pointer to the representative of the set currently containing x.

Convention for measuring cost: let n = the number of makeSet calls, and m = the total number of all three kinds of calls (m ≥ n, and since every UNION reduces the number of sets by exactly one, at most n−1 UNIONs are ever possible). We assume all n makeSet calls happen first, before any UNION or findSet.

These three operations are representation-agnostic — we introduce them before committing to how the sets are stored. Watch a short sequence of all three, drawn simply as labelled groups (no particular representation yet):

An edge case worth seeing on its own: what findSet and a "no-op" UNION do when nothing has been merged yet, and what a caller-side check does if you UNION two elements that are already in the same set (UNION presumes the two sets are distinct, so in real code that check is the caller's job):

Try your own sequence of operations (separate the operations with semicolons: makeSet x, union x y, findSet x):

The convention n, m in code

Elements are plain list indices 0..n-1 (element labels are just names). The next panel builds NaiveDisjointSet (shown in full in section 2): its constructor performs the n makeSet calls, every UNION removes exactly one set, so at most n−1 UNIONs can succeed.

Input size → what is feasible: n, m ≤ 10³ → any representation works; n, m = 10⁶ → you need the forest with both heuristics (sections 5–7). The animations above use n ≤ 6, m ≤ 11.

2. Application: connected components

The flagship application of the three operations is connectedComponents(g) for an undirected graph g whose edges may arrive dynamically (contrast with a DFS-based approach, which needs the whole graph up front):

In words: give every vertex its own singleton set first. Then, for every edge (u, v), check whether u and v are already in the same set — if they are not, that edge connects two previously-separate components, so UNION them. By the time every edge has been processed, two vertices are in the same disjoint-set-structure set exactly when they are in the same connected component of G.

A normal example — a graph with two separate components, one of which needs two merging edges:

Edge cases, part 1: a graph with no edges at all (every vertex its own component, and no UNION ever runs):

Edge cases, part 2: redundant edges — a triangle (the third edge connects two vertices already in the same set) plus a self-loop (3,3), neither of which triggers a UNION:

Try your own graph — enter the number of vertices and a comma-separated edge list like 0-1, 1-2, 3-4:

Counting the calls in code

findSet is called twice per edge and UNION once per edge that joins two different components. The function counts them, and the second panel checks both formulas on this page’s graph (V = 5, E = 4, k = 2 components).

Input size → what is feasible: V ≤ 10⁵ and E ≤ 2·10⁵ → the loop makes 2E = 4·10⁵ findSet calls, instantaneous with the forest of section 5; with the plain array version of the next card a bad edge order can make each findSet walk V steps, so use it only for V ≤ a few thousand.

class NaiveDisjointSet {
  final List<int> parent;
  NaiveDisjointSet(int n) : parent = List<int>.generate(n, (i) => i);
  void makeSet(int x) => parent[x] = x;
  int findSet(int x) {
    while (parent[x] != x) { x = parent[x]; }
    return x;
  }
  void union(int x, int y) {
    final rx = findSet(x), ry = findSet(y);
    if (rx != ry) parent[rx] = ry;
  }
}

List<List<int>> connectedComponents(int n, List<List<int>> edges) {
  final ds = NaiveDisjointSet(n);
  for (final e in edges) {
    if (ds.findSet(e[0]) != ds.findSet(e[1])) ds.union(e[0], e[1]);
  }
  final groups = <int, List<int>>{};
  for (var v = 0; v < n; v++) {
    groups.putIfAbsent(ds.findSet(v), () => <int>[]).add(v);
  }
  return groups.values.toList();
}

sameComponent(u, v) is the one-line payoff: once connectedComponents has finished (or at any point while edges are still arriving), answering "are u and v connected?" is just comparing two findSet results. A normal example — some pairs that ARE in the same component, some that are not, on the graph built above:

Edge cases: asking sameComponent about a vertex and itself (always TRUE, since findSet(u) trivially equals findSet(u)), and asking about two vertices in a graph with zero edges (always FALSE unless they are the same vertex, since nothing has ever been merged):

Try your own graph and your own query pair — enter the number of vertices, an edge list, then |, then u,v:

same component in Dart

The whole procedure is the one comparison on the last line (build once, then compare two findSet results):

Input size → what is feasible: V, E ≤ 5000 → rebuilding on each call costs at most E·V = 2.5·10⁷ steps; for many queries keep the structure and answer each in one findSet pair. The examples above have V ≤ 5, E ≤ 3.

3. The linked-list representation & naive UNION

In the linked-list representation each set is a singly linked list; the set object has pointers to the head (the representative) and tail of the list; every list node stores its member and a back-pointer to the set object. makeSet and findSet are both O(1) (findSet just follows x's back-pointer to the set object, then reads its head). The three panels below describe the operations in pseudocode. As usual, unionNaive(x, y) assumes x and y are in different sets; calling it on two members of the same list would splice a list onto itself and create a cycle, so the animations below skip such a call and say so.

makeSet(x) on lists, animated: each call allocates a fresh set object and a one-node list, and never touches any existing list (so it is O(1) however many sets exist). Normal run, then the smallest possible run, then your own elements:

findSet(x) on lists, animated: one line, two pointer hops (x → its set object → head), independent of how long the list is. First on a merged list, then on a singleton, then your own forest of lists:

The naive UNION's cost is Θ(length of y's list) — every one of y's members needs its back-pointer rewritten (lines 6–7). A single UNION can be fast if y's list happens to be short. But watch what happens with an unlucky ordering — a normal small union first, then a classic worst-case sequence, the countdown order (n makeSet calls, then union(n−2, n−1), union(n−3, n−2), …, always appending the ever-growing list onto the next fresh singleton):

Try your own small worst-case size with naive union (kept small on purpose — watch how fast the update count grows even from n = 10 to n = 20):

The linked-list representation in Dart

The class keeps, for every element, a reference to its set object (the back-pointer x.set); a set object is a list of members, head first. findSet returns the head, unionNaive appends y’s list onto x’s, unionWeighted (section 4) appends the shorter onto the longer. backPointerUpdates counts the relabelling loop, the only non-constant part.

The countdown arithmetic as code: 1 + 2 + … + (n−1) = n(n−1)/2 back-pointer updates for the naive union (2016 for n = 64), only n−1 for the weighted union on the same ordering, and (n/2)·lg n for the balanced worst case of the weighted union.

Input size → what is feasible: n = 20 → 190 relabellings (the slider above); n = 10⁵ → n²/2 = 5·10⁹ relabellings with the naive union (too slow) but only n lg n ≈ 1.7·10⁶ with the weighted union.

4. The weighted-union heuristic

Weighted-union heuristic: maintain each set object's length; on UNION, always append the shorter list onto the longer one (break ties arbitrarily):

The weighted-union bound: with the linked-list representation and the weighted-union heuristic, a sequence of m makeSet/UNION/findSet operations, n of which are makeSet calls, takes O(m + n lg n) time total. Proof idea: whenever some object's back-pointer gets updated, it was a member of the smaller of the two lists just merged — so its set at least doubled in size at that instant. A set can double at most ⌈lg n⌉ times before exceeding the maximum possible size n, so any one object is relabelled at most ⌈lg n⌉ times across the whole sequence. Summed over all n objects, that is O(n lg n) total relabelling work; every makeSet/findSet/UNION record-keeping step besides the relabelling loop is O(1), contributing O(m). Total: O(m + n lg n).

A normal example first — a handful of unequal-size lists merging, always picking up the longer list and walking only the shorter one:

Edge cases: unioning a singleton with a singleton (tie — 1 relabelling either way), and calling UNION on two elements that already share a list. UNION assumes distinct sets, so on its own the pseudocode would splice the list onto itself; the animation shows the caller-side guard that skips such a call:

Run the exact same countdown ordering from section 3, but with weighted union this time — for this ordering the growing list is always the longer one, so only the fresh singleton is ever relabelled and the total collapses from quadratic to just n−1 (Θ(n), as you can see). The true worst case for weighted union, which shows the O(n lg n) bound is tight, needs equal-size merges: type N balanced (for example 16 balanced) to merge singletons pairwise, then pairs of pairs, and so on — every element gets relabelled once per level, for (N/2)·lg N total. Try 16, 64, 16 balanced and 64 balanced:

The weighted-union bound in code

Each relabelling is charged to the element whose back-pointer is rewritten; the panel counts them per element and checks the bound ⌈lg n⌉ on a balanced merge (n = 64 reaches it: 6) and on 200 random sequences.

Input size → what is feasible: n ≤ 64 in the player above; with n = 10⁶ elements each is relabelled at most ⌈lg n⌉ = 20 times, so at most 2·10⁷ relabellings in total.

class LLSet {
  final List<int> members; // head first
  LLSet(int x) : members = [x];
}

class LinkedListDisjointSet {
  final List<LLSet> setOf;
  int backPointerUpdates = 0;
  LinkedListDisjointSet(int n) : setOf = List.generate(n, (i) => LLSet(i));
  int findSet(int x) => setOf[x].members.first;
  void unionWeighted(int x, int y) {
    final sx = setOf[x], sy = setOf[y];
    if (identical(sx, sy)) return;
    final LLSet longer, shorter;
    if (sx.members.length >= sy.members.length) { longer = sx; shorter = sy; }
    else { longer = sy; shorter = sx; }
    for (final m in shorter.members) { setOf[m] = longer; backPointerUpdates++; }
    longer.members.addAll(shorter.members);
  }
}

5. Disjoint-set forests & union by rank

A disjoint-set forest: each node points only to its parent; a root is its own parent and represents the set. makeSet makes a singleton tree; naive UNION just points one root at the other — no better than the linked list's worst case (a chain of n nodes is possible after n−1 UNIONs). Heuristic 1 — union by rank: give every node a rank (an upper bound on its height, not an exact subtree size); always make the smaller-rank root point at the larger-rank root; on a tie, pick either and bump the winner's rank by 1.

findSet(x) without compression, animated: the loop climbs parent pointers until it reaches a node that is its own parent, so the cost is the height of x’s tree (at most ⌊lg n⌋ with union by rank). Nothing is modified. A deep node, then a root (zero hops), then your own forest:

makeSet(x) on the forest is just two assignments: x becomes its own parent (so it is a root) and its rank starts at 0. A normal run — five fresh elements, each becoming a one-node tree (each node is drawn as a circle with its rank rN above it; roots have a thick accent outline):

Edge case: makeSet on a new element while older trees already exist. The newcomer starts with rank 0 even though the older roots have rank 1 — it joins the forest as a separate tree and nothing else is touched:

Try your own list of elements to create (integers 0–15, separated by spaces; a repeated element is rejected, because makeSet requires x not to be in any set already):

union(x, y) is the single line link(findSet(x), findSet(y)): first find the two roots, then LINK them. Here findSet is the plain walk-up version (compression comes in section 6). A normal run — pair up 8 elements, then merge the pairs:

Edge cases: a small tree hung under a big one (ranks differ, so no rank changes), a tie, and a call on two elements that are already in the same set (a caller error — the animation shows what LINK would do and why we skip it):

Try your own sequence — type the number of elements (2–16) and then one UNION x y per item, items separated by semicolons (the box is a single line):

link(x, y) on its own, with x and y already roots. A normal example, drawn as a forest with each node's rank labelled (rN) and roots outlined in the accent colour (the animation calls a silent find to locate the roots, then animates only LINK):

The worst case for union-by-rank alone (the equal-rank pairing): merging trees of equal rank two at a time (like combining binomial trees) really can build a tree of height lg n, so a single findSet can still cost Θ(lg n) — much better than the linked list's Θ(n), but not yet constant:

Try LINK yourself: type the number of elements (2–16) and then one LINK x y per item, items separated by semicolons. Both arguments must currently be roots and different from each other — that is LINK's precondition, and the parser tells you when you break it:

Rank bounds in code

The rank bound (rank ≤ ⌊lg n⌋) and the equal-rank pairing that builds height lg n, as code. buildTall(16) performs exactly the pairing used by the animations: the chain from element 0 has 4 pointers and the root has rank 4 = ⌊lg 16⌋. The arrays parent[x] and rank[x] are plain 0-indexed lists.

Input size → what is feasible: n ≤ 16 in the players; with n = 10⁶ union by rank alone keeps every tree at height ≤ 19, so a findSet costs at most 20 steps without any compression.

class DisjointForest {
  final List<int> parent;
  final List<int> rank;
  DisjointForest(int n)
      : parent = List<int>.generate(n, (i) => i),
        rank = List<int>.filled(n, 0);
  void makeSet(int x) { parent[x] = x; rank[x] = 0; }
  int findSetPlain(int x) {
    while (parent[x] != x) { x = parent[x]; }
    return x;
  }
  void link(int x, int y) {
    if (rank[x] > rank[y]) { parent[y] = x; }
    else {
      parent[x] = y;
      if (rank[x] == rank[y]) rank[y] = rank[y] + 1;
    }
  }
  void unionByRankNoCompression(int x, int y) {
    final rx = findSetPlain(x), ry = findSetPlain(y);
    if (rx != ry) link(rx, ry);
  }
}

6. Path compression

Heuristic 2 — path compression: during findSet(x), after finding the root, make every node visited along the way point directly at that root. It is written as a clean 2-pass recursion (the recursive call finds the root first; then, unwinding, each node's parent is set directly to that root):

Path compression changes parent pointers but never touches rank — ranks stay exactly what union by rank alone would have made them (they become upper bounds rather than exact heights once compression starts shortening real heights below what rank claims, which is fine — rank was only ever an upper bound).

A normal example: one findSet call on a moderately deep tree, shown step by step as the recursion unwinds and each node's arrow snaps straight to the root:

Edge case: findSet when there is nothing to compress — first on a root itself (the if-test fails at once), then on a child that already points straight at the root (the assignment rewrites the same value):

The dramatic case: the tall rank-lg(n) tree built in section 5's worst-case example, before and after path compression — watch every node on the longest chain flatten to point directly at the root in one findSet call:

Try findSet with compression yourself: type the number of elements (2–16), then any number of UNION x y items separated by semicolons (union by rank, no compression, built silently), and and finally exactly one FIND x item whose call is animated:

Path compression in code

The flattening seen in the animation, measured: before the findSet the chain from element 0 has 4 pointers (0→1→3→7→15), afterwards every node of that path points straight at the root and no rank changed.

Input size → what is feasible: the recursion is as deep as the tree is high: ≤ ⌊lg n⌋ = 19 for n = 10⁶ when union by rank is used, but up to n for compression alone, which can exhaust the call stack on a very long chain (the exact limit depends on the platform and settings, but chains of 10⁵ nodes are unsafe), so use an iterative version there.

int findSetCompressed(int x) {
  if (parent[x] != x) {
    parent[x] = findSetCompressed(parent[x]);
  }
  return parent[x];
}

7. Both heuristics together — your own sequence

Now put union by rank and path compression to work together on a sequence you choose. Enter a number of elements and a list of operations (separated by semicolons: UNION x y or FIND x); makeSet for every element runs automatically first. Watch ranks (rN under each node) and the forest's shape evolve, and watch FIND commands flatten whatever path they touch:

Both heuristics together in Dart

UNION with both heuristics is link(findSet(x), findSet(y)) where findSet compresses. The panel checks that it answers every query like the plain array version on 200 random sequences of 60 operations.

Input size → what is feasible: n, m ≤ 10⁶ → about m·α(n) ≤ 4·10⁶ pointer steps in total; the player above takes n ≤ 16.

8. Analysis: the almost-linear α(n)

Define, for k ≥ 0 and j ≥ 1: A₀(j) = j+1, and for k ≥ 1, A_k(j) = A_k−1 applied to itself (j+1) times, starting from j (written A_k−1^(j+1)(j)). Two closed forms make this concrete (provable by induction, and checked numerically in verify/c21.dart): A₁(j) = 2j+1 and A₂(j) = 2^j+1(j+1) − 1. Watch how fast A_k(1) explodes as k climbs from 0 to 4 — this IS the visual explanation of why α(n) stays tiny, without proving the full theorem:

A_k and α(n) in Dart

The definition Ak(j) = Ak−1(j+1)(j) as a recursive function (BigInt, because the values explode; maxIter stops runaway loops, so it is exact only while intermediate values stay below 5000):

α(n) = min{k : Ak(1) ≥ n} with the small table A0(1) .. A3(1) = 2, 3, 7, 2047 (anything above 2047 gives 4):

The closed forms and the growth claims checked numerically, including m·α(n) against m·lg n for n = 10⁶:

Input size → what is feasible: every n you can store (n ≤ 2⁶³) has α(n) ≤ 4, so m·α(n) ≤ 4m — for m = 10⁶ operations that is at most 4·10⁶ steps.

The inverse function: α(n) = min{k : A_k(1) ≥ n}. Because A_k(1) grows so fast, this table covers every practical value of n:

A₄(1) is so large (A₄(1) ≫ 10⁸⁰, and 10⁸⁰ is roughly the estimated number of atoms in the observable universe) that α(n) ≤ 4 for every n that could ever be written down, e.g. every n ≤ 10⁸⁰ — hence "α(n) ≤ 4 for all practical purposes," even though α is technically unbounded as n → ∞ (it is not a constant function; it just grows breathtakingly slowly).

Numerically, the table below (computed live on this page with a seeded random generator) and verify/c21.dart (300 more randomized operation sequences in Dart) both confirm that every node's rank stays ≤ ⌊lg n⌋ — never once exceeding the ⌊lg n⌋ bound, however the random UNION/findSet calls are interleaved — and that the bound is reached exactly by the equal-rank pairing sequence:

9. Off-line minimum with disjoint sets

Given the numbers 1..n and a fixed sequence of n INSERTs interleaved with m extractMin calls (each key inserted exactly once, always before whichever extractMin removes it), offLineMinimum figures out — using only a disjoint-set forest, no heap at all — which key each extractMin would return. The trick: group the keys by which "slot" between two extractMin calls they were inserted into (slot j = keys inserted after the j-th extractMin, counting from 0, and before the next one); represent the m+1 slots as a disjoint-set forest; process keys 1, 2, …, n in increasing order, and for each key, findSet which slot it currently belongs to — that slot number is exactly when it gets extracted (or "never", if it lands in slot m). Once a slot's key has been assigned, merge that slot forward into the next one, so future finds skip over it.

The procedure in pseudocode, where slot j (0 ≤ j ≤ m) is the set of keys inserted after the j-th extractMin (counting from 0) and before the next one, slot m holds the keys inserted after the last extractMin, and slotOf[key] says where each key was inserted:

Line 2 is a find on the disjoint-set structure and line 5 is a link, so a disjoint-set forest with union by rank and path compression (and a label recording each set’s open slot) gives an O(n·α(n)) bound; the simpler Dart below links slot j straight to j+1 and uses path compression only, which is O(n log n) — still tiny. Here is a worked example, sequence 6, 2, E, 7, 1, E, E, 8, 4, 3, E, 5, E (E = extractMin) on keys 1..8, traced key by key (the answer table follows below):

Edge case: keys that land in the last slot after merges. In 5 E 4 E 3 2 E 1 the keys 1 and 3 are never extracted (1 was inserted after the last E; 3 is swallowed into the last set when 2 is extracted):

Try your own sequence — numbers are INSERTs (each of 1..n exactly once, where n is how many numbers you give) and E is extractMin; every E must find at least one key present:

offLineMinimum in Dart

seq holds a positive number for INSERT i and 0 for extractMin. Slot j (0-indexed, 0 ≤ j ≤ m) is a set in a parent-pointer forest; a slot that has been emptied is linked forward to slot j+1, so find(slotOf[key]) is the first still-open slot at or after the key’s own slot. The returned list is extracted[0..m-1].

Input size → what is feasible: n ≤ 10⁴ keys → about n lg n ≈ 1.3·10⁵ steps (a heap simulation would be O(n lg n) too, but this method needs no comparisons at all); the players above take at most 24 tokens.

Quiz

Interview questions

Cheat sheet

α(n) ≤ 4 for every n ≤ 10⁸⁰ (indeed for every n up to A₄(1), which is vastly larger than 10⁸⁰) — so "O(m·α(n))" is, in every practical sense, O(m). In the path-compression-only row, f is the number of findSet operations.