Understanding Union find

Introduction

Union-Find, also known as Disjoint Set Union (DSU), is a data structure that efficiently performs two operations:

1. Find: Determines which set a particular element belongs to.
2. Union: Merges two sets into one.

This structure is widely used in network connectivity problems, Kruskal’s algorithm for Minimum Spanning Trees, and dynamic connectivity.

Core Concepts

Union-Find maintains a collection of disjoint sets. Each set has a representative, which is used to identify the set. The two primary optimizations used are:

Path Compression

Path compression flattens the structure of the tree whenever find() is called, making future operations faster.

Union by Rank

Union by rank ensures that the smaller tree is always attached under the larger tree, keeping the tree height minimal.

Implementation

Below is an implementation of Union-Find in JavaScript:

class UnionFind {
  constructor(size) {
    this.parent = Array.from({ length: size }, (_, i) => i);
    this.rank = Array(size).fill(1);
  }

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

  union(x, y) {
    let rootX = this.find(x);
    let rootY = this.find(y);
    if (rootX !== rootY) {
      if (this.rank[rootX] > this.rank[rootY]) {
        this.parent[rootY] = rootX;
      } else if (this.rank[rootX] < this.rank[rootY]) {
        this.parent[rootX] = rootY;
      } else {
        this.parent[rootY] = rootX;
        this.rank[rootX] += 1;
      }
    }
  }
}

Usage Example

const uf = new UnionFind(5);
uf.union(0, 1);
uf.union(1, 2);
console.log(uf.find(2)); // Output: 0 (or the representative of the set)

Time Complexity

• Find operation: (O(\log n)) (amortized (O(1)) with path compression)
• Union operation: (O(\log n)) (amortized (O(1)) with union by rank)

These optimizations make Union-Find very efficient in practice.

Applications

• Kruskal’s algorithm (Minimum Spanning Tree)
• Network connectivity problems
• Dynamic connectivity queries
• Cycle detection in graphs

Conclusion

Union-Find is a powerful data structure that plays a crucial role in many algorithms. By leveraging path compression and union by rank, it allows near-constant time operations, making it extremely efficient for dynamic connectivity problems.