Disjoint Set Union (Union-Find) with Path Compression

1. Tracking Dynamic Connected Components

The Disjoint Set Union (DSU) data structure (also called Union-Find) maintains a collection of disjoint (non-overlapping) sets. It supports two primary operations:

• find(x): Determine which set element x belongs to (returns representative root).
• union(x, y): Merge the set containing x with the set containing y.

2. Path Compression & Union by Rank

Without optimizations, tree depths can degenerate to O(N). Two optimizations make DSU run in near O(1) amortized time (O(α(N)) Inverse Ackermann function):

1. Path Compression: Flattens the tree during find() so every visited node points directly to the root.
2. Union by Rank: Always attaches the smaller tree under the root of the deeper tree.

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

  find(x) {
    // Path compression: Point node directly to root!
    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; // Already in the same set!

    // 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.numComponents--;
    return true;
  }
}

const dsu = new DisjointSet(5);
dsu.union(0, 1);
dsu.union(1, 2);
console.log(dsu.find(0) === dsu.find(2)); // Output: true (0 and 2 are connected!)
console.log(dsu.find(0) === dsu.find(3)); // Output: false

3. Applications

• Kruskal's Algorithm for Minimum Spanning Trees (MST).
• Redundant Connection Detection (Detecting cycles in undirected graphs).
• Social Network Friends Circles.

4. Common Mistakes

• Forgetting Path Compression: Omitting path compression in find() degrades performance to O(N) on deep linear chains.

5. Next Steps

Use DSU for instant network connectivity queries. Next, let's explore Dynamic Programming: Memoization vs. Tabulation!