Union Find (Disjoint Set Union)

What is this?

Imagine a room full of strangers who keep discovering they're long-lost cousins. Every time two of them learn they're related, their whole families merge into one bigger family. Union-Find is exactly that bookkeeping: it tracks who belongs to which group, lets you merge two groups instantly, and lets you check whether two people are already in the same group. It is the fastest way to answer "are these two things connected?" as connections keep arriving.

💡 Fun fact: the near-instant speed of Union-Find comes with a famously weird footnote. Its true running time involves the inverse Ackermann function, which grows so unimaginably slowly that for any number of items that could ever physically exist, its value is at most 4 — making each operation "effectively constant time."

🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: Union-Find maintains a partition of n elements into disjoint groups under two operations — union(a, b) merges the groups of a and b, and find(x) returns a canonical representative ("root") of x's group. Two elements are connected iff they share a root. With path compression and union by rank/size, both operations run in amortized near-O(1) — and a single integer "component count" answers "how many groups are left?" for free.

1. What Union-Find (Disjoint Set Union) really means

Each element points at a parent; follow parents until you hit a node that points at itself — that's the group's root. A group is therefore a little rooted tree, and the whole structure is a forest of such trees.

find(x) walks x up to its root. union(a, b) finds both roots and, if different, points one root at the other — merging two trees into one.

Two optimizations keep the trees flat (and the cost tiny):

• Path compression (inside find): after locating the root, re-point every node on the path directly at the root, so future finds are near-instant.
  
• Union by rank/size: always hang the shorter/smaller tree under the taller/larger root, so trees never grow unnecessarily tall.

2. Where you'll actually meet this

Disjoint-set thinking is the backbone of "is everything connected, and into how many pieces?" at scale:

• Distributed systems. Connected-components over a node/link graph, network-partition detection (did the cluster split into ≥2 groups?), and Kruskal's MST for building a minimum-cost spanning overlay all sit directly on Union-Find. Component count == 1 means "fully reachable."
• Networking. Loop detection in switch fabrics and merging IP/subnet equivalence classes — a new link that joins two already-connected nodes is a redundant loop.
• Image / data processing. Connected-component labelling (flood-fill regions), clustering by transitive "same-as" relations (entity resolution, dedup).
• Build / package systems. Grouping mutually dependent modules; detecting that adding a dependency would merge cycles.
• Finance / compliance. Grouping accounts by transitive ownership/relationship; flagging that two "separate" entities are actually one connected group.

If a problem says connected, components, merge, same group, cycle on an undirected/streamed edge list — reach for Union-Find before BFS/DFS.

3. The Union-Find toolkit

1. Parent array. parent = list(range(n)) — each element starts as its own root (n singleton groups).
2. find with path compression. Climb to the root, then flatten the path. The one-liner recursive form:

   def find(self, x):
       if self.parent[x] != x:
           self.parent[x] = self.find(self.parent[x])   # compress on the way up
       return self.parent[x]
   

3. union by rank (or size). Merge roots, shorter under taller (rank) or smaller under bigger (size); return False if already merged — that "already same root" is your cycle / redundant-edge signal.

   def union(self, x, y):
       rx, ry = self.find(x), self.find(y)
       if rx == ry:
           return False                       # same group ⇒ cycle / redundant
       if self.rank[rx] < self.rank[ry]:
           rx, ry = ry, rx
       self.parent[ry] = rx
       if self.rank[rx] == self.rank[ry]:
           self.rank[rx] += 1
       self.components -= 1                    # one fewer group
       return True
   

4. The near-O(1) result. Path compression and union by rank together give an amortized cost of O(α(n)) per operation, where α is the inverse Ackermann function — α(n) ≤ 4 for any n you will ever see. Effectively constant.
5. The "count components" trick. Start components = n; decrement on every successful union. At the end, components is the number of disjoint groups — == 1 means fully connected, which is the heart of both problems in this chapter.

4. A 30-second worked example

Five elements 0..4; apply union(0,1), union(2,3), union(1,2), then find(3) and check connected(0,3). Watch components fall from 5 toward the answer.

Three unions, one find, one connectivity query — all amortized near-constant, and the running components counter told us the graph is not fully connected (node 4 is alone).

5. Problems in this chapter

▶ Graph Valid Tree

Decide whether an undirected edge list forms a tree (think: a loop-free, fully-connected fiber backbone across racks). Lead with the counting law — len(edges) != n-1 → instant false — then union each edge, rejecting any edge whose endpoints already share a root (that's a cycle). Survive all n-1 unions ⇒ one component ⇒ tree.
Pattern: cycle-detection-on-union + n-1/connectivity. Target: O(n + m·α(n)), O(n).

▶ Validate Binary Tree Nodes

Verify that directed parent→child links form exactly one valid binary tree (think: a task-orchestration plan with one entry point, no double-owned job, no cyclic trigger chain). Guard ≤ 1 parent per node with a flag, reject the cycle on a same-root union, and require components == 1 at the end (connected + single-root).
Pattern: indegree guard + Union-Find connectivity/cycle. Target: O(n·α(n)), O(n).

Both reduce a "is this a valid tree?" question to the same two Union-Find signals: a same-root union means a cycle, and a final component count of 1 means connected.

6. Common pitfalls 🚫

• Skipping an optimization. Path compression without union by rank (or vice versa) degrades toward O(log n) or even O(n) chains. Use both for the inverse-Ackermann guarantee.
• Forgetting the n-1 / component check. Cycle-free is not the same as connected. A forest of two clean trees has no cycle but isn't one tree — you must also confirm a single component.
• Mutating parent outside union/find. Hand-editing parents breaks the rank invariant and corrupts future merges.
• Treating "already same root" as benign. That return-False is load-bearing — it is your cycle / redundant-edge detector; ignoring it accepts invalid graphs.
• Assuming direction. Union-Find is inherently undirected; for directed problems (like binary-tree validation) layer an indegree/parent guard on top to capture the direction-specific rules.

7. Key takeaways

1. Union-Find = disjoint groups under find + union, with two elements "connected" iff they share a root — the go-to for connectivity, components, and cycle-on-edge questions.
2. Path compression + union by rank/size make operations amortized O(α(n)) — effectively constant; always apply both.
3. A same-root union is a cycle; a component count of 1 is full connectivity — the two signals that solve every problem in this chapter.
4. components = n, decrement on each successful union gives you "how many groups?" for free — the cleanest connectivity proof there is.
5. Reach for it over BFS/DFS when edges stream in, when you must answer "did this edge close a loop?", or when you only need group membership — Union-Find needs no adjacency list and no recursion over the graph.