λDSA Learning Hubpart of DSA Atlas

Union-Find (Disjoint Set Union)

Intermediate~2h · 6 lessons8 practice problems

Near-O(1) dynamic connectivity: merge groups and query membership with path compression and union by rank — the engine behind Kruskal, account merging, and cycle detection.

0 of 6 lessons checked off

Introduction

What it is

  • Union-Find maintains a collection of disjoint sets under two operations: find(x) — which set is x in? — and union(x, y) — merge their sets.
  • Each set is a tree of elements pointing toward a root representative; two elements share a set exactly when find() reaches the same root.

Why it matters

  • It answers dynamic connectivity — edges arriving over time, queries interleaved — where re-running BFS after every change would cost O(V + E) each. With both optimisations, operations cost amortised inverse-Ackermann time: ≤ 5 for any realistic input, effectively O(1).
  • It's the standard tool for: Kruskal's MST, counting components while edges stream in, redundant-connection (cycle) detection, and merging accounts/groups by shared attributes.

How it works

  • parent[i] starts as i (everyone their own root). find follows parents to the root; union links one root under the other.
  • Path compression: while finding, re-point every visited node straight at the root — flattening for the future.
  • Union by rank/size: attach the shorter tree under the taller — preventing chains from forming at all.

Where it's used

  • Network reachability under link additions, image-segmentation region merging, Kruskal inside network design tools, and dedupe systems merging records that share emails/phones.

In interviews

  • Number of connected components (streamed edges), redundant connection, accounts merge, most stones removed, number of islands II (online version).
Analogy: Merging friend circles at a party: each circle has one spokesperson (root). 'Same circle?' — ask each person's spokesperson. When circles merge, one spokesperson defers to the other; path compression is everyone saving the top spokesperson's number directly.

Interactive diagram

union(0,1), union(2,3), union(1,3), union(4,5) — watch roots merge and a redundant union get refused.

012345
6 elements, 6 sets

Every element starts as its own root: parent[i] = i. Two elements are in the same set exactly when find() reaches the same root.

Lessons in this topic

Check off lessons as you go — your progress is saved in this browser.

  1. The forest model: parent array and roots

    Sets as trees; representatives; find by walking up.

    15 min
  2. Why naive union degenerates

    Chained links = O(n) finds — the problem to engineer away.

    10 min
  3. Path compression

    Flatten as you find; amortised magic, two-line change.

    15 min
  4. Union by rank / size

    Attach small under large; height stays O(log n) even alone.

    15 min
  5. Cycle detection via union-find

    An edge whose endpoints already share a root closes a cycle.

    15 min
  6. Components, Kruskal, account merge

    The three canonical deployments.

    25 min

Operations

find + union with both optimisations

find flattens as it walks (compression); union links by rank. Together: amortised α(n) ≈ constant per operation.

012345
6 elements, 6 sets

Every element starts as its own root: parent[i] = i. Two elements are in the same set exactly when find() reaches the same root.

class UnionFind:    """Disjoint sets over 0..n-1. Amortised ~O(1) per op (inverse Ackermann)."""    def __init__(self, n: int) -> None:        self.parent = list(range(n))     # everyone is their own root        self.rank = [0] * n              # tree-height upper bound        self.count = n                   # live component count    def find(self, x: int) -> int:        root = x        while self.parent[root] != root:            root = self.parent[root]        while self.parent[x] != root:    # path compression pass            self.parent[x], x = root, self.parent[x]        return root    def union(self, a: int, b: int) -> bool:        """Merge the sets of a and b. False if already together."""        ra, rb = self.find(a), self.find(b)        if ra == rb:            return False                 # same set — a cycle if (a,b) is an edge        if self.rank[ra] < self.rank[rb]:            ra, rb = rb, ra              # ra is the taller root        self.parent[rb] = ra             # small tree under big tree        if self.rank[ra] == self.rank[rb]:            self.rank[ra] += 1        self.count -= 1        return True    def connected(self, a: int, b: int) -> bool:        return self.find(a) == self.find(b)
Time: Amortised O(α(n)) ≈ O(1) per find/unionSpace: O(n)

Edge cases

  • union of already-connected elements returns False — exactly the cycle signal (Redundant Connection).
  • count starts at n and decrements per successful union — components for free.
  • String/tuple elements: map them to indexes first (or use a parent dict).

Common mistakes

  • Comparing parent[a] == parent[b] instead of find(a) == find(b) — parents aren't roots.
  • Skipping BOTH optimisations: chains form and find degrades to O(n).

Counting components from an edge list

Start with n singletons; each successful union welds two components into one. The counter is the answer — no traversal at all.

Counting components from an edge list
def count_components(n: int, edges: list[list[int]]) -> int:    """Connected components of an undirected graph. O(E α(n))."""    uf = UnionFind(n)    for a, b in edges:        uf.union(a, b)    return uf.countdef has_redundant_edge(edges: list[list[int]]) -> list[int] | None:    """First edge that closes a cycle (Redundant Connection)."""    uf = UnionFind(1 + max(max(e) for e in edges))    for a, b in edges:        if not uf.union(a, b):     # already connected → this edge is the loop            return [a, b]    return None
Time: O(E · α(n)) — effectively linear in edgesSpace: O(n)

Edge cases

  • Isolated vertices (no edges) stay as their own components — n counts them from the start.
  • Duplicate edges: the second union returns False harmlessly.
  • Works online: answer available after any prefix of edges (BFS can't do that without re-running).

Common mistakes

  • Re-running full BFS per edge arrival — the exact O(E·(V+E)) cost union-find eliminates.
  • Sizing the structure by edge count instead of vertex count.

Complexity analysis

OperationBestAverageWorstSpace
find / union / connectedO(1)O(α(n)) ≈ O(1)O(log n) single opO(n)
n unions + m finds (both optimisations)—O((n + m) α(n))O((n + m) α(n))O(n)
Naive (no optimisation) findO(1)O(n)O(n)O(n)

α(n) is the inverse Ackermann function: α(10⁸⁰) ≤ 5. Say 'amortised near-constant, inverse Ackermann' — precise and impressive.

What interviewers expect you to know

What interviewers expect you to know

  • The two optimisations, independently: compression flattens on read, rank prevents chains on write.
  • The cycle idiom: union returning False = edge inside one component = cycle.
  • The live component counter — decrement per successful union.
  • When union-find beats BFS/DFS: edges arrive over time, or you only need grouping, never paths.

Classic follow-ups

  • "What's the complexity, exactly?" — amortised O(α(n)); with rank alone O(log n); naive O(n).
  • "Can you delete an edge?" — plain union-find can't un-merge; offline reversal or link-cut trees exist (naming suffices).
  • "Non-integer elements?" — dict-based parents or an index map.

Common mistakes

Parent checked instead of root

parent[x] is one hop, not the representative. Every membership decision goes through find().

Compression without the second pass

Finding the root but never re-pointing the path wastes the optimisation; the two-loop (or recursive) form re-parents every visited node.

Union by neither rank nor size

Arbitrary root linking builds chains; with compression it mostly survives, but the guaranteed bound is gone. Two extra lines buy the proof.

Using it for shortest paths

Union-find knows THAT things connect, never HOW. Path questions are BFS/Dijkstra territory.

Practice problems

Hand-picked from the 355-problem DSA Atlas. Reveal hints and solutions progressively; mark and bookmark as you solve.

Medium (5)

Hard (3)

Topic quiz

4 questions across concepts, code output, complexity, and scenarios. Answer all, then submit for explanations.

  1. Concept1. union(a, b) returns False in the standard implementation. What did you just learn?
  2. Complexity2. With path compression AND union by rank, m operations over n elements cost…
  3. Scenario3. Edges stream in one by one; after each, you must report the component count. Why union-find over BFS?
  4. Code output4. n=5, unions: (0,1), (2,3), (0,3). How many components remain, and what does union(1,2) now return?
0 of 4 answered

Frequently asked questions

Union by rank or by size — does it matter which?

No — both cap tree height at O(log n) and combine with compression for the α(n) bound. Size has a bonus: you get component sizes for free, which some problems ask for.

Recursive or iterative find?

Recursive `parent[x] = find(parent[x])` is elegant but stacks up on long chains before compression kicks in. The two-loop iterative version is safe at any scale — prefer it in Python.

Union-find or DFS for Number of Islands?

Static grid: DFS/BFS flood fill is simpler. The union-find version shines in Islands II, where land appears incrementally and each addition must report the updated island count.

Summary & cheat sheet

Key takeaways

  • Two ops: find (who's your root?) and union (merge roots) — near-O(1) amortised with both optimisations.
  • union == False ⇒ cycle; a live counter tracks components.
  • Compression flattens on reads; rank prevents chains on writes.
  • Connectivity yes, paths no.
  • It's the online alternative to re-running BFS as edges arrive.

Formulas & cheat sheet

  • components = n − (successful unions)
  • Rank-only height bound: O(log n); with compression: amortised α(n)

Interview checklist

  • I can write UnionFind with both optimisations in under five minutes.
  • I can explain why union returning False means a cycle.
  • I know when to choose it over BFS/DFS (streaming edges, grouping-only).