Disjoint Set (Union-Find)

The Disjoint Set, also known as Union-Find, is a specialized data structure used to track a set of elements partitioned into a number of disjoint (non-overlapping) subsets.

It answers two specific questions with near $O(1)$ blazing speed:

1. Find: Which subset does element A belong to? (Used to check if A and B are in the same subset).
2. Union: Merge the subset containing A with the subset containing B.

Real-Life Analogy

Think of Social Circles at a Party. Initially, everyone arrives alone (each person is their own set).

• Union(Bob, Alice): Bob and Alice start talking. They are now in the same social group.
• Union(Charlie, Alice): Charlie joins the conversation. Now Bob, Alice, and Charlie are all in the same group.
• Find(Bob) == Find(Charlie)? Yes, they are in the same conversation, even if Bob didn't directly talk to Charlie.

The Problem it Solves

If you have a massive Graph, how do you know if there is a path from Node A to Node B? You could run Breadth-First Search (BFS), but that takes $O(V + E)$ time. If you need to answer this question 100,000 times as edges are dynamically added, BFS will be far too slow. Union-Find solves this near-instantly.

It is heavily used to detect cycles in Undirected Graphs and is the core engine behind Kruskal's Minimum Spanning Tree algorithm.

How it Works Under the Hood

Union-Find uses a forest of trees represented entirely inside a flat Array. The array parent[i] stores the parent of element i.

• If parent[i] == i, then i is the Root (or representative) of the set.
• To check if A and B are connected, you find the Root of A, and the Root of B. If they share the exact same Root, they are connected!

The Two Critical Optimizations

If we just union trees naively, they will degenerate into Linked Lists (O(N) time). We apply two optimizations to achieve almost $O(1)$ time:

1. Path Compression (on Find): When you call find(A), you traverse up to the root. But before returning, you rewire A and every node along the path to point directly to the Root! Next time you call find(A), it's instant $O(1)$.
2. Union by Rank/Size: When merging two sets, you always attach the smaller tree under the root of the larger tree. This keeps the trees incredibly shallow.

Implementation in TypeScript

class UnionFind {
  private root: number[];
  private rank: number[]; // Used to track tree depth

  constructor(size: number) {
    this.root = new Array(size);
    this.rank = new Array(size);
    // Initially, every element is its own root
    for (let i = 0; i < size; i++) {
      this.root[i] = i;
      this.rank[i] = 1;
    }
  }

  // The FIND function (With Path Compression!)
  public find(x: number): number {
    if (x === this.root[x]) {
      return x; // Reached the absolute root!
    }
    // Path Compression: Point directly to root as we return
    this.root[x] = this.find(this.root[x]); 
    return this.root[x];
  }

  // The UNION function (With Union by Rank!)
  public union(x: number, y: number): void {
    let rootX = this.find(x);
    let rootY = this.find(y);

    if (rootX !== rootY) {
      // Attach the smaller tree under the larger tree
      if (this.rank[rootX] > this.rank[rootY]) {
        this.root[rootY] = rootX;
      } else if (this.rank[rootX] < this.rank[rootY]) {
        this.root[rootX] = rootY;
      } else {
        // If they are equal, attach one to the other and increase rank
        this.root[rootY] = rootX;
        this.rank[rootX] += 1;
      }
    }
  }

  // Utility to check connection
  public connected(x: number, y: number): boolean {
    return this.find(x) === this.find(y);
  }
}

Time Complexity

With both Path Compression and Union by Rank applied, the amortized time complexity for both find and union drops to $O(\alpha(N))$, where $\alpha$ is the Inverse Ackermann function. For all practical values of N in the physical universe, $\alpha(N) \le 4$. Therefore, it is effectively $O(1)$ Constant Time!