Disjoint Set (Union-Find)
with Union by Rank, Size and Path Compression

Problem Statement

The Disjoint Set (also called Union-Find) is a data structure used to manage a collection of non-overlapping sets. It supports two main operations:

• Find: Determine which set a particular element belongs to.
• Union: Merge two sets into a single set.

Disjoint Set is particularly useful in problems involving connected components, cycle detection in graphs, and Kruskal's algorithm for Minimum Spanning Tree.

To improve efficiency, it uses two optimizations:

• Union by Rank or Union by Size: Always attach the smaller tree under the root of the larger tree.
• Path Compression: Flatten the tree whenever Find is used, making future queries faster.

Algorithm Steps

1. Initialization: Set each node as its own parent and rank/size as 1.
2. Find(x):
   1. If x is not the parent of itself, recursively call Find on its parent.
   2. Apply path compression by setting the parent of x to the result of Find.
3. Union(x, y):
   1. Find roots of both x and y.
   2. If they are the same, no union is needed (already connected).
   3. Else, attach the smaller rank/size tree under the larger one.
   4. If ranks are equal, arbitrarily choose one and increment its rank.

Code

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

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

  union(x, y) {
    let rootX = this.find(x);
    let 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]++;
    }
  }
}

const ds = new DisjointSet(5);
ds.union(0, 1);
ds.union(1, 2);
console.log("Find(2):", ds.find(2)); // Should be 0
console.log("Find(3):", ds.find(3)); // Should be 3 (not connected)