Union-Find (DSU) — the shape behind dozens of interview problems.

Union-Find (DSU) in Python

class DSU:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n
    def find(self, x: int) -> int:
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            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
        if self.rank[ra] < self.rank[rb]: ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        return True

See language-specific tabs at /languages/python/patterns and the SQL variant at /languages/sql/patterns.

Related patterns

Frequently asked questions

What is the union-find (dsu) pattern?

Union-Find (DSU) is a disjoint-set data structure supporting near-constant merge and find. Amortized O(α(n)) per op with path compression + union by rank.

When should I use union-find (dsu)?

Use it when: Connectivity queries on a graph that only grows. Counting connected components. Detecting cycles as edges arrive (e.g., Kruskal's MST).

What are the most common union-find (dsu) bugs?

Skipping path compression → O(log n) amortized degrades to O(n) on bad input. Union by rank reversed (parenting the larger tree to the smaller). Returning the wrong component representative after a lazy merge.

What problems use the union-find (dsu) pattern?

Representative scenarios: Friend-Circle Counter — count connected people clusters. Extra Cable Finder — detect redundant edges. LAN Mesh Audit — validate full connectivity after merges.

Is union-find (dsu) on the Blind 75?

Yes — Union-Find (DSU) is one of the core patterns behind the Blind 75 list. See /blind-75 for the complete mapping.