Union-Find (DSU)

TL;DR

Disjoint-Set Union (DSU), a.k.a. Union-Find, is a parent[] array that encodes a forest of trees, one tree per equivalence class. find(x) walks parent pointers up to the root — that root is the canonical name of x’s set. union(a, b) is “find both roots, hang one under the other.” Two elements are in the same component iff find(a) == find(b).

The naive version is O(n) per call because the trees can grow tall. Two optimisations fix that. Path compression rewrites parent[x] to the root during every find, flattening the tree as a side effect of querying it. Union by rank (or size) always hangs the shorter tree under the taller one, so trees stay shallow on the way up. Together they give O(α(n)) amortised per operation — α is the inverse Ackermann function, which is ≤ 4 for any input you’ll ever see. Effectively O(1).

The reason to reach for DSU instead of BFS/DFS is online connectivity: edges arrive one at a time and you have to answer “are these two connected?” between insertions. You can’t preprocess the graph because the graph doesn’t exist yet. DSU lets you incrementally merge components as edges stream in and answer same-set queries in constant time at any point.

It’s also the spine of Kruskal’s MST, cycle detection in undirected graphs, connected-component labelling in image processing, and any clustering algorithm that’s “merge things that touch.”

When to reach for it

Signals that DSU is the right tool:

• Edges arrive over time. You’re processing a stream of pairs and need to answer connectivity queries interleaved with insertions. BFS/DFS would force a re-scan per query.
• “Is this edge redundant?” — i.e. does it close a cycle in an undirected graph? find(u) == find(v) before union(u, v) is the test. This is LeetCode 684 verbatim.
• Kruskal’s MST. Sort edges by weight, take each edge whose endpoints are in different sets, union them. DSU is what makes the “different set?” check fast.
• “How many connected components?” Initialise a counter to n, decrement on every successful union (one that actually merged two distinct sets). The counter is the answer at any moment.
• Equivalence classes more abstract than graph nodes. Email-account merging (LC 721), variable unification in a type checker, equating congruent grid cells in a flood fill — anything where “x and y are the same thing now” is the core operation.

If the graph is fixed and you need shortest paths or traversal order, DSU isn’t the answer — BFS/DFS is.

Flavor 1 — minimal DSU with path compression and union by rank

class DSU:
    def __init__(self, n: int) -> None:
        self.parent = list(range(n))   # each node is its own root
        self.rank = [0] * n            # upper bound on tree height

    def find(self, x: int) -> int:
        # path compression: rewrite parent[x] to root on the way up
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, a: int, b: int) -> bool:
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False               # already same set; no merge
        # union by rank: shorter tree hangs under taller
        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

union returns True on a real merge, False if the two were already in the same set — that boolean is exactly the redundant-edge / cycle-detection signal you want for Kruskal and LC 684.

Worked example. n = 6, operations [(0,1), (2,3), (0,2), (4,5)]. Track parent and rank after each call.

After step 4 there are two components: {0,1,2,3} rooted at 0, and {4,5} rooted at 4. Note that parent[3] is still 2, not 0 — path compression only fires when somebody actually calls find(3). Call it once and parent[3] rewrites to 0. The lazy compression is the point: you pay only on access.

A query like find(1) == find(3) returns True (both reach root 0), while find(1) == find(5) returns False. Both run in effectively constant time.

Flavor 2 — Kruskal’s MST

DSU is the engine inside Kruskal. Sort edges by weight, greedily take every edge whose endpoints are in different sets, stop after n - 1 edges accepted.

def kruskal_mst(n: int, edges: list[tuple[int, int, int]]) -> list[tuple[int, int, int]]:
    # edges: (weight, u, v)
    edges.sort()
    dsu = DSU(n)
    mst = []
    for w, u, v in edges:
        if dsu.union(u, v):           # only accept edges that merge sets
            mst.append((w, u, v))
            if len(mst) == n - 1:
                break
    return mst

The union boolean does double duty: it merges the component and tells us whether the edge is safe to add. Total cost is O(E log E) for the sort plus O(E α(n)) for the unions — the sort dominates.

Flavor 3 — DSU with size for “largest component”

When the question is “what’s the size of the biggest component?” or “how big is x’s component?”, track size instead of (or alongside) rank.

class DSUSize:
    def __init__(self, n: int) -> None:
        self.parent = list(range(n))
        self.size = [1] * 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
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        return True

size[find(x)] is the size of x’s component. The max(size[i] for i in range(n) if parent[i] == i) (or just track a running max in union) gives you the largest. Path halving — parent[x] = parent[parent[x]] — is a one-pass alternative to two-pass compression; slightly less aggressive but still α(n) amortised, and easier to write in a tight loop.

Pick rank or size based on what the problem asks. Don’t carry both unless you actually need both.

Why it works — the invariant

The single invariant: find(x) returns the canonical root of x’s set, and two elements have the same root iff they’re in the same set. Every operation preserves it. union merges two roots, after which both subtrees agree on the new root. find walks pointers up to that root — the walk is correct regardless of how compressed the tree is.

Path compression is purely an optimisation on top of correctness. After find(x), every node on the path from x to the root points directly at the root, so the next find on any of them is O(1). Union by rank keeps the uncompressed tree height at O(log n), so even the first find after a union is cheap. Combine the two and Tarjan’s analysis gives the inverse-Ackermann amortised bound — the proof is technical but the intuition is “compression makes future finds cheap, rank keeps current finds cheap, and the two reinforce each other.”

Complexity

• Time: O(α(n)) amortised per find and per union. α(n) ≤ 4 for n ≤ 2^65536, so treat it as O(1) in practice. A sequence of m operations on n elements is O((m + n) α(n)).
• Space: O(n) for parent, plus O(n) for rank or size.
• Without compression or rank: O(n) worst case per find — the tree degenerates to a linked list. Without compression but with rank: O(log n). Always implement both if you can.

Common pitfalls

• Path compression on union without calling find first. Writing parent[a] = b directly skips the root lookup and corrupts the forest. Always go through find(a) and find(b) and union the roots, not the raw arguments.
• Mixing rank and size semantics. Rank is a height upper bound; size is a node count. They’re updated differently (rank only increments on ties; size always sums). Pick one and be consistent — interleaving the two breaks the height bound.
• Off-by-one on init. parent[i] = i for i in range(n). If you forget and leave zeros, every node thinks node 0 is its parent and your forest collapses on the first find. list(range(n)) is the only safe initialiser.
• Trying to “un-union.” DSU has no efficient deletion. Once two sets merge, splitting them requires rebuilding from the original edge list minus the one you want to drop. If your problem deletes edges over time, reach for link-cut trees or offline reverse-time processing — not DSU.
• Forgetting union returns false on same-set. The boolean is the cycle / redundant-edge signal. Throwing it away and then doing a separate find(a) == find(b) check before each union is a common beginner pattern that doubles the work.

Where you see this in production

• Kruskal-based MST in network topology design. Telco backbone planning, datacentre cable layout, and distributed-systems gossip overlays use Kruskal-with-DSU to pick a minimum-weight spanning set of links. The DSU is what makes “would adding this link create a redundant loop?” cheap.
• OpenCV connected components. cv2.connectedComponents and the underlying two-pass labelling algorithm use union-find to merge equivalent labels discovered during the first scan. Same idea drives scikit-image’s label() and most image-segmentation pipelines.
• Boost Graph Library disjoint_sets. The reference C++ DSU implementation, used inside BGL’s Kruskal, biconnected-component, and incremental-connectivity algorithms. Templated on rank and parent property maps so you can plug it into any graph representation.
• Hindley-Milner type unification. OCaml, Haskell, and Rust’s trait-resolution code all use union-find to merge type variables during inference. When the unifier discovers 'a = int, it unions the two representatives so every later lookup sees the same canonical type.

Practice problems

Resources

• NeetCode roadmap — neetcode.io/roadmap — pattern-by-pattern problem sets organised exactly like this site.
• NeetCode practice grid — neetcode.io/practice — track which problems you’ve solved per pattern.
• NeetCode YouTube — @NeetCode — clear, whiteboard-style walkthroughs for almost every LeetCode problem above.
• William Fiset — Union-Find — www.youtube.com