Union-Find Variants — Path Compression, Union by Rank

Union by rank

int find(int x) {
  if (parent[x] != x) parent[x] = find(parent[x]);
  return parent[x];
}
void union(int x, int y) {
  int px = find(x), py = find(y);
  if (px == py) return;
  if (rank[px] < rank[py]) parent[px] = py;
  else if (rank[px] > rank[py]) parent[py] = px;
  else { parent[py] = px; rank[px]++; }
}

Union by size

Alternative to rank: track subtree size, attach smaller to larger. Also O(α(N)) amortized.

Path halving

Instead of full compression, halve path: parent[x] = parent[parent[x]]. Simpler, similar performance.

Weighted union-find

Track weight relative to root. Useful for arithmetic constraints. Sum along path during find.