Disjoint Set Union, also known as Union-Find, is a data structure that tracks a set of elements partitioned into several non-overlapping (disjoint) subsets.

Think of Nations merging together:

1. At the start, every person is their own nation. They are the Leader of themselves.
2. If Nation A and Nation B decide to merge, they pick one Leader. Let's say A becomes the leader.
3. If someone asks: "Who is the leader of B?", the answer is now A.
4. Union: Merging two nations.
5. Find: Finding the "Ultimate Leader" of a person. If two people have the same Ultimate Leader, they are in the same nation!

---

Optimizations

1. Path Compression: When finding the leader, make every node on the path point directly to the ultimate leader. This flattens the tree.
2. Union by Rank/Size: Always attach the smaller tree under the root of the larger tree. This keeps the tree short.

Complexity

With both optimizations, the complexity is $O(\alpha(n))$ per operation, where $\alpha$ is the Inverse Ackermann function. For all practical purposes, this is $O(1)$.

---

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

  // Find with Path Compression
  find(i) {
    if (this.parent[i] === i) return i;
    this.parent[i] = this.find(this.parent[i]);
    return this.parent[i];
  }

  // Union by Rank
  union(i, j) {
    const rootI = this.find(i);
    const rootJ = this.find(j);

    if (rootI !== rootJ) {
      if (this.rank[rootI] < this.rank[rootJ]) {
        this.parent[rootI] = rootJ;
      } else if (this.rank[rootI] > this.rank[rootJ]) {
        this.parent[rootJ] = rootI;
      } else {
        this.parent[rootI] = rootJ;
        this.rank[rootJ]++;
      }
      return true; // Union successful
    }
    return false; // Already in the same set
  }
}

---

Top Use Cases

• Cycle Detection in an Undirected Graph (If find(u) === find(v), adding edge uv creates a cycle).
• Kruskal's Algorithm for Minimum Spanning Tree.
• Number of Connected Components.
• Social Network connectivity (Friend of a Friend).

Common Questions

• Explain the logic of Path Compression.
• Why do we use rank/size for union?
• What is the time complexity of Union-Find? 🤝