Union-Find (Disjoint Set Union)

Merging groups efficiently

Union-find, also called disjoint set union (DSU), maintains a collection of non-overlapping groups and supports two operations: find(x), which returns a representative (root) of x's group, and union(a, b), which merges the groups of a and b. Each element points to a parent, and roots point to themselves. Two optimisations make it extremely fast: path compression (during find, point visited nodes directly at the root) and union by rank or size (attach the smaller tree under the larger). Together they give an amortised cost per operation of O(α(n)), where α is the inverse Ackermann function, which is less than 5 for any practical n, so effectively constant. Union-find answers "are these two connected?" as edges arrive, without re-running a graph search. Applications include Kruskal's minimum spanning tree, detecting cycles in undirected graphs, grouping duplicate accounts or records that share an email or phone number, network connectivity, image segmentation and percolation simulations.

Union-find forest

Each group is a tree; find follows parents to the root, and path compression flattens the path.

Merging customer accounts that share contact details

Union by size with path compression.

class UnionFind:
    def __init__(self):
        self.parent: dict[str, str] = {}
        self.size: dict[str, int] = {}

    def find(self, x: str) -> str:
        if x not in self.parent:
            self.parent[x], self.size[x] = x, 1
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:               # path compression
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, a: str, b: str) -> bool:
        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 under larger
        self.size[ra] += self.size[rb]
        return True

accounts = [
    ("acc1", ["asha@x.com", "+91-90000-00001"]),
    ("acc2", ["asha.work@x.com", "+91-90000-00001"]),   # shares a phone with acc1
    ("acc3", ["ravi@x.com"]),
    ("acc4", ["asha.work@x.com"]),                     # shares an email with acc2
]

uf = UnionFind()
for acc, contacts in accounts:
    for contact in contacts:
        uf.union(acc, contact)

groups: dict[str, list[str]] = {}
for acc, _ in accounts:
    groups.setdefault(uf.find(acc), []).append(acc)
print(list(groups.values()))      # [['acc1', 'acc2', 'acc4'], ['acc3']]

Cycle detection for free

When adding an undirected edge (u, v), if find(u) == find(v) already, the edge would create a cycle. Kruskal's algorithm uses exactly this check to build a minimum spanning tree.

त्वरित जाँच: Which two optimisations make union-find operations nearly constant time?

• Path compression and union by rank or size
• Sorting and hashing
• Recursion and memoisation
• Binary search and heaps