Union-find (disjoint set)

Merge groups and ask 'same group?' in near-constant time.

The tell: Connectivity queries, redundant edges, accounts merging, or Kruskal's MST.

Reach for it when

Number of connected components
Detecting a cycle in an undirected graph
Kruskal's minimum spanning tree
Accounts merge / equations satisfiability

Reference implementation

DSU — path compression and union by size

class DSU:
    def __init__(self, n: int) -> None:
        self.parent = list(range(n))
        self.size = [1] * n
        self.components = n

    def find(self, x: int) -> int:
        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: int, b: int) -> bool:
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                                    # already joined
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        self.components -= 1
        return True

Complexity: Near O(1) amortised per operation with path compression + union by rank.

What goes wrong

Skipping path compression — worst case degrades to O(n) per find.
Attaching the larger tree under the smaller one, which defeats union by size.
Using union-find on a directed graph, where 'connected' does not mean what you think.

Practise on

Number of Provinces
Redundant Connection
Accounts Merge
Number of Islands II

Test yourself on DSA Next pattern: Backtracking →