Patternwise

Union-Find (DSU)

Every group elects a leader; merging means one leader bows.

Brute force
O(E·(V + E)) — re-run BFS/DFS after each edge
With the pattern
O(E · α(V)) ≈ O(E) — near-constant per operation
Extra space
O(V)

In plain English

“At a party, everyone points to a friend who points to someone else, until you reach the group's host. To check if two guests are in the same group, follow the pointing to each host. When two groups meet, one host just starts pointing at the other host — and guests who walked the chain start pointing closer to the host so next time it's quicker.”

Why it's fast

Re-running BFS after every new edge to check connectivity costs O(V + E) each time. Union-Find answers "same group?" and "merge groups" in nearly O(1) amortized, thanks to path compression (or path halving) and union by size/rank. Counting components is just: start at n, subtract 1 each time a union actually merges two different roots.

Spot it when the problem says…

  • number of connected components / provinces
  • edges arrive one by one (dynamic connectivity)
  • redundant connection / creates a cycle
  • group accounts / emails that share something
  • are x and y connected
  • minimum cost to connect all (Kruskal)

Visualize

Counting connected components

8 nodes, a list of edges. How many separate groups are there?

graph (colour = group)

0root1root2root3root4root5root6root7root

parent[]

0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
01/14

Every node starts as its own group: parent[i] = i. 8 components.

pythonline 2
1def count_components(n, edges):2    parent = list(range(n))3    def find(x):4        while parent[x] != x:5            parent[x] = parent[parent[x]]   # path halving6            x = parent[x]7        return x8    components = n9    for a, b in edges:10        ra, rb = find(a), find(b)11        if ra != rb:12            parent[ra] = rb                 # union13            components -= 114    return components

variables

components
8

How to apply it

  1. 01Initialize parent[i] = i and size[i] = 1; components = n.
  2. 02find(x): walk up to the root, halving the path as you go.
  3. 03union(a, b): find both roots; if equal, they're already connected (cycle!).
  4. 04Otherwise attach the smaller tree under the larger, and components -= 1.

Variations you'll meet

DSU with path halving + union by size

The visualizer's example — counting components.

python
class DSU:    def __init__(self, n: int):        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]]  # halve            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 connected        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

Cycle detection (Redundant Connection)

The first edge whose union returns False closes a cycle.

Keyed DSU

When nodes are strings (emails), use a dict parent.setdefault(x, x) instead of an array.

Kruskal's MST

Sort edges by weight; add each edge whose endpoints are in different sets.

Common mistakes

  • Setting parent[a] = b instead of parent[find(a)] = find(b) — merges nodes, not groups.
  • Decrementing the component count even when both nodes already share a root.
  • Skipping path compression and union by size, degrading to O(n) per find on chains.
  • Comparing parent[a] == parent[b] instead of find(a) == find(b).

Practice ladder

Easy → hard. Tick them off as you go.

0/8 solved
  1. 01Find if Path Exists in Graph ↗Easy
  2. 02Number of Provinces ↗Medium
  3. 03Redundant Connection ↗Medium
  4. 04Number of Operations to Make Network Connected ↗Medium
  5. 05Satisfiability of Equality Equations ↗Medium
  6. 06Accounts Merge ↗Medium
  7. 07Most Stones Removed with Same Row or Column ↗Medium
  8. 08Swim in Rising Water ↗Hard

Think you've got it?

Let the AI interviewer throw a Union-Find (DSU) problem at you and grade how you explain it.

Mock interview