A+DS

Union-Find

Track connected components efficiently.

Union-Find (Disjoint Set Union) tracks a collection of non-overlapping sets. It supports two operations: Union merges two sets, and Find determines which set an element belongs to. With union by rank and path compression, both operations run in nearly O(1) amortized time.

  Before Union(0,2):      After Union:
    {0,1}  {2,3}            {0,1,2,3}
      0      2                  0
      |      |                / | \
      1      3               1  2  3

  Find(3) with compression:
    3 → 2 → 0  →  3 → 0 (direct!)

How it works

  1. 1Each element starts in its own set (parent = self)
  2. 2Find(x): follow parent pointers to the root
  3. 3Path compression: point every node on the path directly to root
  4. 4Union(x,y): link the root of smaller-rank tree under larger-rank tree

Loading...