Union-Find

Union-Find (Disjoint Set Union)

Union-Find is a data structure that tracks elements partitioned into disjoint (non-overlapping) sets. It supports two primary operations efficiently:

• find(x) — determine which set x belongs to (returns the root representative).
• union(x, y) — merge the sets containing x and y.

Key Optimizations

Union by Rank: Always attach the shorter tree under the root of the taller tree. This keeps trees shallow.

Path Compression: During find, make every node on the path point directly to the root. This flattens the structure for future queries.

find(x) {
  if (this.parent[x] !== x) {
    this.parent[x] = this.find(this.parent[x]); // path compression
  }
  return this.parent[x];
}

union(x, y) {
  const rootX = this.find(x);
  const rootY = this.find(y);
  if (rootX === rootY) return;
  // union by rank
  if (this.rank[rootX] < this.rank[rootY]) this.parent[rootX] = rootY;
  else if (this.rank[rootX] > this.rank[rootY]) this.parent[rootY] = rootX;
  else { this.parent[rootY] = rootX; this.rank[rootX]++; }
}

Complexity

Where α is the inverse Ackermann function — effectively constant for all practical inputs.

Real-World Uses

• Network connectivity (are two computers connected?)
• Kruskal's minimum spanning tree algorithm
• Image processing (connected components)
• Social network friend groups

Your Task

Implement a UnionFind class with find, union, and connected methods using union by rank and path compression.