​

Union-Find (Disjoint Set Union)

​

Core Operations

​

Optimizations

• Path Compression — during find, point every node directly to the root
• Union by Rank/Size — attach the smaller tree under the root of the larger tree

​

Implementation

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        return True

​

Classic Problems

• Number of Connected Components
• Redundant Connection (cycle detection)
• Accounts Merge
• Longest Consecutive Sequence
• Number of Islands (alternative to BFS/DFS)
• Kruskal’s Minimum Spanning Tree
• Satisfiability of Equality Equations

​

When to Use

• Dynamic connectivity — are two nodes in the same group?
• Cycle detection in undirected graphs
• Merging groups or components incrementally
• Kruskal’s MST algorithm
• Problems where you need to track connected components over time