Union Find (Disjoint Set) - Complete Guide

Union Find (Disjoint Set Union, DSU) is a data structure for tracking elements partitioned into disjoint sets. It efficiently handles union and find operations.

What is Union Find? #

A data structure that maintains a collection of disjoint (non-overlapping) sets and supports two operations:

  • Find - Determine which set an element belongs to
  • Union - Merge two sets into one

Applications:

  • Detect cycles in graphs
  • Find connected components
  • Kruskal’s MST algorithm
  • Network connectivity
  • Image processing

Basic Implementation #

class UnionFind {
  constructor(size) {
    this.parent = Array.from({ length: size }, (_, i) => i);
    this.count = size;  // Number of disjoint sets
  }

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

  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);

    if (rootX === rootY) {
      return false;  // Already connected
    }

    this.parent[rootX] = rootY;
    this.count--;
    return true;
  }

  connected(x, y) {
    return this.find(x) === this.find(y);
  }

  getCount() {
    return this.count;
  }
}

// Usage
const uf = new UnionFind(5);
uf.union(0, 1);
uf.union(1, 2);
console.log(uf.connected(0, 2));  // true
console.log(uf.connected(0, 3));  // false
console.log(uf.getCount());  // 3 sets

Path Compression #

Optimize find operation by flattening tree structure.

class UnionFind {
  constructor(size) {
    this.parent = Array.from({ length: size }, (_, i) => i);
    this.count = size;
  }

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

  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);

    if (rootX === rootY) {
      return false;
    }

    this.parent[rootX] = rootY;
    this.count--;
    return true;
  }
}

Union by Rank #

Attach smaller tree under root of larger tree.

class UnionFind {
  constructor(size) {
    this.parent = Array.from({ length: size }, (_, i) => i);
    this.rank = new Array(size).fill(0);
    this.count = size;
  }

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

  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);

    if (rootX === rootY) {
      return false;
    }

    // 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]++;
    }

    this.count--;
    return true;
  }
}

Union by Size #

Track size of each set.

class UnionFind {
  constructor(size) {
    this.parent = Array.from({ length: size }, (_, i) => i);
    this.size = new Array(size).fill(1);
    this.count = size;
  }

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

  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);

    if (rootX === rootY) {
      return false;
    }

    // Union by size
    if (this.size[rootX] < this.size[rootY]) {
      this.parent[rootX] = rootY;
      this.size[rootY] += this.size[rootX];
    } else {
      this.parent[rootY] = rootX;
      this.size[rootX] += this.size[rootY];
    }

    this.count--;
    return true;
  }

  getSize(x) {
    return this.size[this.find(x)];
  }
}

const uf = new UnionFind(5);
uf.union(0, 1);
uf.union(1, 2);
console.log(uf.getSize(0));  // 3
console.log(uf.getSize(3));  // 1

Number of Connected Components #

function countComponents(n, edges) {
  const uf = new UnionFind(n);

  for (const [u, v] of edges) {
    uf.union(u, v);
  }

  return uf.getCount();
}

console.log(countComponents(5, [[0, 1], [1, 2], [3, 4]]));  // 2
console.log(countComponents(5, [[0, 1], [1, 2], [2, 3], [3, 4]]));  // 1

Detect Cycle in Undirected Graph #

function hasCycle(n, edges) {
  const uf = new UnionFind(n);

  for (const [u, v] of edges) {
    if (!uf.union(u, v)) {
      return true;  // Cycle detected
    }
  }

  return false;
}

console.log(hasCycle(3, [[0, 1], [1, 2], [2, 0]]));  // true
console.log(hasCycle(3, [[0, 1], [1, 2]]));  // false

Redundant Connection #

Find edge that creates cycle.

function findRedundantConnection(edges) {
  const n = edges.length;
  const uf = new UnionFind(n + 1);

  for (const [u, v] of edges) {
    if (!uf.union(u, v)) {
      return [u, v];  // This edge creates cycle
    }
  }

  return [];
}

console.log(findRedundantConnection([[1, 2], [1, 3], [2, 3]]));  // [2, 3]
console.log(findRedundantConnection([[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]));  // [1, 4]

Accounts Merge #

function accountsMerge(accounts) {
  const emailToName = new Map();
  const emailToId = new Map();
  let id = 0;

  // Map emails to IDs
  for (const account of accounts) {
    const name = account[0];
    for (let i = 1; i < account.length; i++) {
      const email = account[i];
      if (!emailToId.has(email)) {
        emailToId.set(email, id++);
        emailToName.set(email, name);
      }
    }
  }

  const uf = new UnionFind(id);

  // Union emails from same account
  for (const account of accounts) {
    const firstEmail = account[1];
    const firstId = emailToId.get(firstEmail);

    for (let i = 2; i < account.length; i++) {
      const email = account[i];
      uf.union(firstId, emailToId.get(email));
    }
  }

  // Group emails by root
  const groups = new Map();
  for (const [email, emailId] of emailToId) {
    const root = uf.find(emailId);
    if (!groups.has(root)) {
      groups.set(root, []);
    }
    groups.get(root).push(email);
  }

  // Create result
  const result = [];
  for (const emails of groups.values()) {
    emails.sort();
    result.push([emailToName.get(emails[0]), ...emails]);
  }

  return result;
}

const accounts = [
  ['John', 'john@mail.com', 'john_work@mail.com'],
  ['John', 'john@mail.com', 'john@other.com'],
  ['Mary', 'mary@mail.com']
];

console.log(accountsMerge(accounts));
// [['John', 'john@mail.com', 'john@other.com', 'john_work@mail.com'], ['Mary', 'mary@mail.com']]

Friend Circles #

function findCircleNum(isConnected) {
  const n = isConnected.length;
  const uf = new UnionFind(n);

  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      if (isConnected[i][j] === 1) {
        uf.union(i, j);
      }
    }
  }

  return uf.getCount();
}

const isConnected = [
  [1, 1, 0],
  [1, 1, 0],
  [0, 0, 1]
];

console.log(findCircleNum(isConnected));  // 2

Number of Islands #

function numIslands(grid) {
  if (grid.length === 0) return 0;

  const rows = grid.length;
  const cols = grid[0].length;
  let waterCells = 0;

  const uf = new UnionFind(rows * cols);

  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (grid[i][j] === '0') {
        waterCells++;
      } else {
        // Union with right neighbor
        if (j + 1 < cols && grid[i][j + 1] === '1') {
          uf.union(i * cols + j, i * cols + j + 1);
        }
        // Union with bottom neighbor
        if (i + 1 < rows && grid[i + 1][j] === '1') {
          uf.union(i * cols + j, (i + 1) * cols + j);
        }
      }
    }
  }

  return uf.getCount() - waterCells;
}

const grid = [
  ['1', '1', '0', '0', '0'],
  ['1', '1', '0', '0', '0'],
  ['0', '0', '1', '0', '0'],
  ['0', '0', '0', '1', '1']
];

console.log(numIslands(grid));  // 3

Optimize Water Distribution #

function minCostToSupplyWater(n, wells, pipes) {
  // Add virtual node 0 connected to all wells
  const edges = [];

  for (let i = 0; i < wells.length; i++) {
    edges.push([0, i + 1, wells[i]]);
  }

  for (const [house1, house2, cost] of pipes) {
    edges.push([house1, house2, cost]);
  }

  // Sort edges by cost
  edges.sort((a, b) => a[2] - b[2]);

  // Kruskal's algorithm
  const uf = new UnionFind(n + 1);
  let totalCost = 0;
  let edgesUsed = 0;

  for (const [u, v, cost] of edges) {
    if (uf.union(u, v)) {
      totalCost += cost;
      edgesUsed++;
      if (edgesUsed === n) break;
    }
  }

  return totalCost;
}

console.log(minCostToSupplyWater(3, [1, 2, 2], [[1, 2, 1], [2, 3, 1]]));  // 3

Satisfiability of Equality Equations #

function equationsPossible(equations) {
  const uf = new UnionFind(26);

  // Process equality equations
  for (const eq of equations) {
    if (eq[1] === '=') {
      const x = eq.charCodeAt(0) - 'a'.charCodeAt(0);
      const y = eq.charCodeAt(3) - 'a'.charCodeAt(0);
      uf.union(x, y);
    }
  }

  // Check inequality equations
  for (const eq of equations) {
    if (eq[1] === '!') {
      const x = eq.charCodeAt(0) - 'a'.charCodeAt(0);
      const y = eq.charCodeAt(3) - 'a'.charCodeAt(0);
      if (uf.find(x) === uf.find(y)) {
        return false;
      }
    }
  }

  return true;
}

console.log(equationsPossible(['a==b', 'b!=a']));  // false
console.log(equationsPossible(['a==b', 'b==c', 'a==c']));  // true

Smallest String With Swaps #

function smallestStringWithSwaps(s, pairs) {
  const n = s.length;
  const uf = new UnionFind(n);

  // Union indices that can be swapped
  for (const [i, j] of pairs) {
    uf.union(i, j);
  }

  // Group indices by root
  const groups = new Map();
  for (let i = 0; i < n; i++) {
    const root = uf.find(i);
    if (!groups.has(root)) {
      groups.set(root, []);
    }
    groups.get(root).push(i);
  }

  // Sort characters in each group
  const result = s.split('');

  for (const indices of groups.values()) {
    const chars = indices.map(i => s[i]).sort();
    indices.sort((a, b) => a - b);

    for (let i = 0; i < indices.length; i++) {
      result[indices[i]] = chars[i];
    }
  }

  return result.join('');
}

console.log(smallestStringWithSwaps('dcab', [[0, 3], [1, 2]]));  // 'bacd'
console.log(smallestStringWithSwaps('dcab', [[0, 3], [1, 2], [0, 2]]));  // 'abcd'

Most Stones Removed #

function removeStones(stones) {
  const n = stones.length;
  const uf = new UnionFind(n);

  // Union stones in same row or column
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      if (stones[i][0] === stones[j][0] || stones[i][1] === stones[j][1]) {
        uf.union(i, j);
      }
    }
  }

  return n - uf.getCount();
}

console.log(removeStones([[0, 0], [0, 1], [1, 0], [1, 2], [2, 1], [2, 2]]));  // 5

Optimized Version with Coordinate Mapping #

function removeStones(stones) {
  const uf = new Map();

  function find(x) {
    if (!uf.has(x)) {
      uf.set(x, x);
    }
    if (uf.get(x) !== x) {
      uf.set(x, find(uf.get(x)));
    }
    return uf.get(x);
  }

  function union(x, y) {
    uf.set(find(x), find(y));
  }

  for (const [x, y] of stones) {
    // Use ~y to distinguish from x coordinates
    union(x, ~y);
  }

  const roots = new Set();
  for (const [x, y] of stones) {
    roots.add(find(x));
  }

  return stones.length - roots.size;
}

Time Complexity #

OperationWithout OptimizationWith Path CompressionWith Both
FindO(n)O(log n)O(α(n))
UnionO(n)O(log n)O(α(n))
SpaceO(n)O(n)O(n)

α(n) = inverse Ackermann function (practically constant)

Best Practices #

  1. Always use path compression - Flatten tree on find
  2. Union by rank or size - Keep trees balanced
  3. Map for non-integer keys - Use coordinate or string keys
  4. Track component count - Decrement on successful union
  5. Check before union - Detect cycles
  6. Initialize properly - Each element is own parent
  7. Use for connectivity - Efficient for graph problems

Union Find is essential for graph connectivity problems. With optimizations, it achieves near-constant time operations.

Previous Python - A Comprehensive Introduction Greedy Algorithms - Complete Guide Next