Union-Find — the near-O(1) connectivity structure
Union-Find (DSU)
Union-Find tracks a collection of elements partitioned into groups and answers two questions fast: which group is x in (find), and merge groups of x and y (union). With path compression + union by rank, amortised cost is O(α(n)) — inverse Ackermann, effectively constant.
Sits under Kruskal's MST, cycle detection, dynamic connectivity, image segmentation, account-merge problems.
How it works
Every element points at a parent. Roots point to themselves — group identity. find(x) walks parents to root; path compression re-points nodes on the walk directly at the root.
union(a, b) finds both roots, hangs one under the other. Union by rank always hangs shorter under taller so trees stay flat. Rank is an upper bound on height.
Together: near-constant. Neither alone is enough.
Common bugs
- Recursive
findon deep chains. Iterative is safer for Python's 1000-frame limit. - Union without
findfirst.self.parent[b] = amerges b's local pointer, not its group. - Forgetting "already connected" case. In Kruskal, this creates cycles.
- 1-indexed inputs. Size arrays as
n+1or subtract 1.
Try it
- Add
group_size(x)returning component size. Maintain asizearray updated insideunion. - Build cycle detection for undirected graph: if
union(u, v)returns False, edge closes a cycle.
3 graded exercises
Write the code, click Check. We’ll tell you exactly what to fix.
- Exercise 1
Build a
DSUclass withfind(x)(path compression) andunion(x, y). Support integer nodes 0..n-1 passed to__init__(n). - Exercise 2
Write
dsu_components(n, edges)that returns the number of connected components in an undirected graph withnnodes (0..n-1) and the given edge list. Use union-find. - Exercise 3
Write
find_redundant_edge(edges)for a graph on nodes 1..n formed by adding edges one at a time; exactly one edge creates a cycle. Return that edge (the first one along the input order that connects two already-connected nodes).