What is the Union-Find data structure?

A Union-Find or Disjoint Set Union (DSU) data structure is used to track a set of elements partitioned into a number of disjoint (non-overlapping) subsets. It provides two primary operations: 'find' (determine which subset an element belongs to) and 'union' (join two subsets into a single subset).

What are the key optimizations for Union-Find?

The two most important optimizations are 'path compression' and 'union by size/rank'. Path compression flattens the structure of the tree by making every node point directly to the root. Union by size or rank attaches the smaller tree to the root of the larger tree to keep the trees shallow.

Graph Algorithms

Union-Find (Disjoint Set Union)

An efficient data structure for tracking elements partitioned into disjoint sets, crucial for problems involving connectivity and equivalence.

Union-Find Implementation

This JavaScript implementation of the Union-Find data structure includes path compression and union by size for near-constant time complexity on average.

                            class UnionFind {
                              constructor(size) {
                                this.parent = new Array(size).fill(0).map((_, i) => i);
                                this.size = new Array(size).fill(1);
                              }
                            
                              find(i) {
                                if (this.parent[i] === i) {
                                  return i;
                                }
                                this.parent[i] = this.find(this.parent[i]); // Path compression
                                return this.parent[i];
                              }
                            
                              union(i, j) {
                                const rootI = this.find(i);
                                const rootJ = this.find(j);
                                if (rootI !== rootJ) {
                                  // Union by size
                                  if (this.size[rootI] < this.size[rootJ]) {
                                    this.parent[rootI] = rootJ;
                                    this.size[rootJ] += this.size[rootI];
                                  } else {
                                    this.parent[rootJ] = rootI;
                                    this.size[rootI] += this.size[rootJ];
                                  }
                                }
                              }
                            }
                        

AI Coach Hint: The combination of path compression and union by size/rank makes the Union-Find data structure's operations run in nearly constant time on average (amortized), making it incredibly efficient for problems like detecting cycles in a graph or network connectivity.