Union-Find

Connected components and dynamic connectivity in near-constant time.

Union-find (disjoint set union) tracks which elements belong to the same group, supporting two operations in nearly constant time: find (which group is x in?) and union (merge two groups). It shines when connections arrive one at a time and you need to answer connectivity questions along the way.

When to use it

Counting connected components as edges are added
"Are these two nodes connected?" asked many times
Detecting a cycle in an undirected graph (an edge between two nodes already in the same set)
Grouping by shared attributes — accounts sharing an email, similar strings
Kruskal's minimum spanning tree

Implementation

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.components = n

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

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                 # already connected
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra             # attach smaller tree under larger
        self.size[ra] += self.size[rb]
        self.components -= 1
        return True

With both optimizations, operations run in O(α(n)) — the inverse Ackermann function, effectively constant.

Mapping non-integer keys

For strings or emails, assign each a numeric ID on first sight (ids.setdefault(email, len(ids))), or implement the parent map as a dictionary.

Union-find vs DFS

For a static graph, BFS/DFS counts components just as well. Union-find wins when edges arrive incrementally ("after each new land cell, how many islands?") or when the grouping is defined by shared keys rather than an explicit graph.

[!TIP] Practice Accounts Merge · Number of Islands (try the union-find version)