Union-Find / Disjoint Set

Groups as trees

Union-Find (Disjoint Set Union) represents each group as a tree, where every node points to a parent, and the root is its own parent. find(x) walks up to the root to identify x's group; union(x, y) links one root under the other.

Path compression + union by rank

Two optimizations make this near-constant time: path compression flattens the tree during find, and union by rank attaches the smaller tree under the bigger one.

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

Output:

uf = UnionFind(5)
uf.union(0, 1)
uf.find(0) == uf.find(1)  # True

Where it's used

Detecting cycles in an undirected graph, Kruskal's MST, counting connected components, and 'friend circles' style problems all lean on Union-Find.

Quick check

Test your understanding of amortized complexity.

Quick check: With path compression and union by rank, find/union run in roughly:

• O(n)
• O(log n)
• O(n log n)
• Nearly O(1) (inverse-Ackermann)