Union-Find (Disjoint Set Union)

Union-Find is a data structure that tracks elements partitioned into disjoint sets. It supports two operations: union (merge two sets) and find (determine which set an element belongs to).

When to Use

Problems involving connected components
Cycle detection in undirected graphs
Dynamic connectivity queries
Minimum spanning tree (Kruskal's algorithm)

Common Patterns

Basic Union-Find

Track connected components with path compression

Example: Number of provinces, redundant connection

Weighted Union-Find

Union by rank/size for better balance

Example: Optimize tree depth

Code Templates

Python

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n  # Number of components
    
    def find(self, x):
        """Find with path compression"""
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        """Union by rank"""
        root_x = self.find(x)
        root_y = self.find(y)
        
        if root_x == root_y:
            return False  # Already connected
        
        # Union by rank
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1
        
        self.count -= 1
        return True
    
    def connected(self, x, y):
        """Check if x and y are in same set"""
        return self.find(x) == self.find(y)
    
    def get_count(self):
        """Return number of disjoint sets"""
        return self.count

C++

class UnionFind {
private:
    vector<int> parent;
    vector<int> rank;
    int count;  // Number of components
    
public:
    UnionFind(int n) : parent(n), rank(n, 0), count(n) {
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    
    // Find with path compression
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    // Union by rank
    bool unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        
        if (rootX == rootY) {
            return false;  // Already connected
        }
        
        // Union by rank
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        
        count--;
        return true;
    }
    
    // Check if x and y are in same set
    bool connected(int x, int y) {
        return find(x) == find(y);
    }
    
    // Return number of disjoint sets
    int getCount() {
        return count;
    }
};