Union–Find (DSU)

How it works, step by step

1. 1

   Start with every item as its own set: each item's parent pointer points at itself, which makes it a root.

2. 2

   find(x): follow parent pointers from x until you reach a node that points at itself. That root is the set's name.

3. 3

   union(x, y): find both roots. If they are the same root, x and y are already connected - do nothing (this is also how you detect a cycle).

4. 4

   Different roots? Attach one root under the other. Union by size: always hang the smaller tree under the bigger root, so no node in the bigger tree gets deeper.

5. 5

   Path compression: after every find, re-point each node you walked directly at the root. The tree flattens itself as you use it.

6. 6

   With both tricks, any sequence of operations costs O(α(n)) each on average - and α(n) is at most 4 for any input that fits in this universe.

The code, in JavaScript

function makeSets(n) {
  // parent[i] === i  means  "i is a root"
  return Array.from({ length: n }, (_, i) => i);
}

function find(parent, x) {
  while (parent[x] !== x) x = parent[x];   // climb until a node points at itself
  return x;
}

function union(parent, a, b) {
  const ra = find(parent, a);
  const rb = find(parent, b);
  if (ra === rb) return false;             // already in the same set
  parent[ra] = rb;                         // hang one root under the other
  return true;
}

const p = makeSets(6);       // sets: {0} {1} {2} {3} {4} {5}
union(p, 0, 1);              // {0,1}
union(p, 2, 3);              // {2,3}
union(p, 1, 3);              // {0,1,2,3}
find(p, 0) === find(p, 2);   // → true  (same root)
find(p, 0) === find(p, 4);   // → false (4 is still alone)

Dry run: 6 unions, 2 finds and a connected? check on 8 items

The same steps the visualizer plays, written as a table. Generated by running the real algorithm - not written by hand.

• You need both optimizations. Skip them and a bad union order builds a chain, turning find into an O(n) crawl. Either trick alone gives O(log n); together they give O(α(n)).
• The famous "near O(1)" bound is amortized and only holds with the optimizations. α(n), the inverse Ackermann function, is at most 4 for any n that fits in physical reality - but a plain parent array earns none of that.
• DSU merges, it never splits. If your problem removes edges, do not reach for DSU by reflex - a common trick is to process removals backwards as additions, when the problem allows it.
• Caching roots is a classic stale-value bug. `find(a) === find(b)` is always safe at the moment you call it, but a root you saved in a variable can stop being a root after the very next union.

Union–Find (DSU) vs. its closest relatives