Union-Find (DSU)

O(α(n)) per op

Union-Find (a disjoint-set union) maintains a collection of disjoint sets, drawn here as a forest where each set is a tree and its root is the representative. find(x) follows parent pointers up to the root; union(a, b) links the root of one tree under the other. Two optimisations make it almost O(1) per operation (inverse-Ackermann, α(n)): union by size always attaches the smaller tree beneath the larger so trees stay shallow, and path compression re-points every node visited during a find straight at the root, flattening the tree for next time. It underlies Kruskal's MST, connected-components, cycle detection, and image segmentation. Roots are ringed; the active find path is teal.

u a b = union · f a = find (0–9)
Disjoint-set forest
Edit the input and press Play

How it works

  1. Every element starts as its own one-node set (its own root).
  2. find(x) walks up parent pointers to the root, then compresses the path.
  3. union(a, b) finds both roots and links the smaller tree under the larger.
  4. Unioning elements already in the same set changes nothing.

Pseudocode

1unionFind:                          # ~O(1) amortised per op2  parent[i] = i, size[i] = 1        # n singleton sets3  find(x): follow parent to the root,4           then point the path straight at it  # path compression5  union(a, b): r1 = find(a), r2 = find(b)6    attach the smaller tree under the larger    # union by size