Disjoint Set Union (Union-Find) with Path Compression

Dynamic Arrays & Amortized Resizing

Learn how dynamic arrays achieve O(1) amortized insertion, contiguous memory layout, and geometric doubling strategies.

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(alpha(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!