09 — Union-Find (Disjoint Set Union)

What is Union-Find?

Data structure to track disjoint sets with near-O(1) operations.

Initially: {0} {1} {2} {3} {4}
union(0,1): {0,1} {2} {3} {4}
union(2,3): {0,1} {2,3} {4}
union(1,3): {0,1,2,3} {4}
find(0) === find(3)? → true (same set)
find(0) === find(4)? → false (different sets)

---

Implementation

class UnionFind {
  private parent: number[];
  private rank: number[];
  public components: number;
  
  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
    this.components = n;
  }
  
  find(x: number): number {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]); // Path compression
    }
    return this.parent[x];
  }
  
  union(x: number, y: number): boolean {
    const px = this.find(x), py = this.find(y);
    if (px === py) return false; // Already in same set
    
    // Union by rank
    if (this.rank[px] < this.rank[py]) this.parent[px] = py;
    else if (this.rank[px] > this.rank[py]) this.parent[py] = px;
    else { this.parent[py] = px; this.rank[px]++; }
    
    this.components--;
    return true;
  }
  
  connected(x: number, y: number): boolean {
    return this.find(x) === this.find(y);
  }
}

Optimizations

---

Cycle Detection in Undirected Graph

function hasCycle(n: number, edges: [number, number][]): boolean {
  const uf = new UnionFind(n);
  
  for (const [u, v] of edges) {
    if (!uf.union(u, v)) return true; // Already connected → cycle
  }
  return false;
}

---

Kruskal's MST (with Union-Find)

function kruskal(n: number, edges: [number, number, number][]): number {
  edges.sort((a, b) => a[2] - b[2]);
  const uf = new UnionFind(n);
  let cost = 0;
  
  for (const [u, v, w] of edges) {
    if (uf.union(u, v)) {
      cost += w;
      if (uf.components === 1) break;
    }
  }
  return cost;
}

---

Number of Connected Components

function countComponents(n: number, edges: [number, number][]): number {
  const uf = new UnionFind(n);
  for (const [u, v] of edges) uf.union(u, v);
  return uf.components;
}

---

Number of Islands (Grid)

function numIslands(grid: string[][]): number {
  const rows = grid.length, cols = grid[0].length;
  const uf = new UnionFind(rows * cols);
  let water = 0;
  
  const dirs = [[0, 1], [1, 0]]; // Only right and down to avoid duplicates
  
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '0') { water++; continue; }
      
      for (const [dr, dc] of dirs) {
        const nr = r + dr, nc = c + dc;
        if (nr < rows && nc < cols && grid[nr][nc] === '1') {
          uf.union(r * cols + c, nr * cols + nc);
        }
      }
    }
  }
  return uf.components - water;
}

---

Union-Find with Size

class UnionFindSize {
  private parent: number[];
  private size: number[];
  
  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.size = new Array(n).fill(1);
  }
  
  find(x: number): number {
    if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]);
    return this.parent[x];
  }
  
  union(x: number, y: number): boolean {
    const px = this.find(x), py = this.find(y);
    if (px === py) return false;
    
    // Union by size (attach smaller to larger)
    if (this.size[px] < this.size[py]) {
      this.parent[px] = py;
      this.size[py] += this.size[px];
    } else {
      this.parent[py] = px;
      this.size[px] += this.size[py];
    }
    return true;
  }
  
  getSize(x: number): number {
    return this.size[this.find(x)];
  }
}

---

Key Takeaways

• Union-Find = near-O(1) merge and query for disjoint sets
• Path compression + union by rank = amortized O(α(n)) ≈ constant
• Use for: cycle detection, MST (Kruskal's), connected components, grid problems
• union returns false if already connected — use for cycle detection
• Track components count to know when the graph is fully connected