Disjoint Set (Union-Find)

Implement a Disjoint Set (Union-Find) over n elements 0 .. n-1:

union(a, b) — merge the sets containing a and b.
connected(a, b) — return whether a and b are in the same set.
components() — return the current number of disjoint sets.

Aim for near-O(1) amortized operations using union by rank/size and path compression.

Hints

· Stuck? Reveal one nudge at a time.

Represent each set by a root; find walks to it, union links two roots.

connected(a, b) is find(a) == find(b); components starts at n and drops on each real union.

Path compression + union by rank keep the trees flat for near-O(1) operations.

Common doubts

They only reshape the internal trees; which elements share a set (and how many sets exist) is determined solely by the sequence of unions.

Both keep trees shallow and give the same near-O(1) guarantee; size (count of nodes) is often easier to maintain.

Unioning two elements already in the same set merges nothing, so the count is unchanged.

Interview follow-ups

· What an interviewer asks next.

It adds an edge only if its endpoints are in different sets (no cycle), unioning them otherwise.

Not directly — you'd need a rollback/persistent DSU that records and undoes unions.

Fun facts

With both optimizations, m operations cost O(m·α(n)) — α grows so slowly it's ≤ 4 for any practical n.
Union-Find is the classic example where a tiny tweak (compression) yields a dramatic speedup.

Asked at

AmazonGoogleMicrosoft

Frequently Sometimes Occasionally

Example 1

Input: DisjointSet(5), unite(0,1), unite(1,2), connected(0,2), components()
Output: null null null true 3
{0,1,2}, {3}, {4} — 0 and 2 share a set; three components remain.

Example 2

Input: DisjointSet(3), connected(0,1), unite(0,1), connected(0,1)
Output: null false null true
Initially separate, then merged.

Constraints

- 1 <= n <= 10^5 - 0 <= a, b < n - At most 2 * 10^4 operations

A Disjoint Set maintains a forest: each element points to a parent, and the root of a tree is its set's representative. find walks to the root; union links one root under another; connected is find(a) == find(b); and a component counter starting at n drops by one on each successful union.

The naive version works but can degrade to O(n) per find on a tall chain. Two optimizations flatten it to near-O(1) amortized (inverse-Ackermann):

Path compression — during find, repoint nodes toward the root so future finds are short.
Union by rank (or size) — attach the shallower tree under the deeper one, so trees stay flat.

Note the connectivity answers (connected, components) are the same regardless of the union heuristic — the heuristics only change the internal tree shape, not which elements share a set.

Prerequisites

Before you start

· Concepts used directly in the solution.

Forest of parents. root = set representative.

Compression + rank. the two flattening optimizations.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“What does components() count?”

The number of disjoint sets currently.

“Do union heuristics change the answers?”

No — only performance; connectivity is the same.

The ideal opening — say it like this

Each element points to a parent; find walks to the root, union links two roots, connected compares roots.

Path compression plus union by rank keep every operation near-constant amortized.

Understand the problem

Worked example — n = 5, then unite(0,1), unite(1,2), connected(0,2), components()

after unions: {0,1,2}, {3}, {4}
connected(0,2) -> true
components() -> 3

Key observations

1Aha

Root = representative

connected(a,b) is find(a) == find(b).

2Aha

Successful union decrements the count

Merging two distinct sets reduces components by one.

3Aha

Compression + rank ⇒ near-O(1)

The two optimizations flatten the forest.

Brute force vs optimal

	Naive union	Rank + path compression
find	O(n) worst case	near-O(1) amortized
union	O(n) worst case	near-O(1) amortized
Answers	same	same

Both give identical connectivity answers; the optimizations only speed them up. Full code is in the Approaches selector below.

Summary

Key takeaway

A parent forest with find/union; connected compares roots and components counts sets. Path compression + union by rank make every operation near-O(1) amortized.

find: walk to root (compressing); union: link roots by rank, cnt--; connected: same root