The Idea

A disjoint-set union structure - DSU, union-find, merge-find - keeps a pile of things partitioned into groups, and answers exactly one question fast: are these two in the same group? It also does exactly one destructive thing: merge two groups into one. That is the whole interface. Everything on the rest of these pages is either how to make those two operations fast, what extra facts you can carry along for free, or how to notice that a problem is secretly asking for them.

This page is the model. Find & Union is the algorithm and the cost; this page is only about what the structure is, and what it refuses to do.

1. The one question it answers

Start from the problem, not the code. You have n things. Facts arrive one at a time, each of the form "these two belong together." At any point you may be asked "do these two belong together?" - where "together" means connected through any chain of the facts you were given, not just a single fact.

Three facts arrive; the fourth question is about a link nobody ever stated.

That transitive closure is the entire difficulty. Storing the raw facts is trivial; answering same(A, C) from them means chasing a chain of arbitrary length. A graph traversal would do it - but it would redo the whole walk on every query, and it needs all the facts up front. DSU precomputes the answer incrementally, so each new fact costs almost nothing and each query is almost free.

A DSU is a set of name tags, not a map of the connections.

It never remembers that A-B was a fact and A-C was an inference. It only remembers, for each element, which group it currently belongs to. Ask it why two things are connected and it has nothing to say - that information was thrown away the moment the fact was absorbed.

2. The forest of parent pointers

The implementation is one array. Each element stores the index of one other element - its parent. Follow parents upward and you eventually reach an element that is its own parent: a root. That root is the group's representative (also: leader, boss, delegate).

parent[] on the left, the forest it encodes on the right. The self-loops are literal: a root's parent is itself.

Two consequences fall straight out of that picture:

• Every arrow points up. A node knows its parent; a parent does not know its children. That asymmetry is what makes the structure cheap and also what it cannot undo.
• Two elements are in the same group exactly when they reach the same root. So same(a, b) is literally find(a) == find(b), and there is nothing else to check.

⚠

The forest is not the graph

The shape of the DSU forest has nothing to do with the shape of the input graph. Nodes 2 and 0 are two hops apart in the picture above, but the fact that created that link may have been a direct edge 0-2. The forest is an accounting artifact - its parent pointers are chosen for balance, not to mirror any edge you were given. Reading a path in the forest as a path in the problem is a real and recurring mistake.

3. The four arrays, and who is allowed to read them

A production DSU carries up to four parallel arrays. Only one of them is required.

Array	Holds
	Valid for
parent[i]	the index of i's parent, or i itself if i is a root. Required.
	every element. This is the structure; everything else is bookkeeping.
rank[i]	an upper bound on the height of the tree rooted at i
	roots only. A non-root's rank is stale garbage that is never read again.
size[i]	how many elements are in the tree rooted at i
	roots only. Same rule: size[x] is meaningless unless find(x) == x.
count	how many groups exist right now (a scalar, not an array)
	always. Starts at n, drops by one per successful merge.

⚠

size[x] is a lie unless x is a root

Read size and rank through find, never directly. size[x] is only the size of x's component when x happens to be that component's root - otherwise it is whatever the value was back when x last was a root, frozen in place. The safe accessor is size[find(x)], and it is worth writing a getSize(x) method purely so you never type the unsafe form. Sizes that come out plausible-but-small are almost always this bug.

4. The invariants

Five statements are true of a DSU at every moment between operations. If you are debugging one, check these before anything else - each has a one-line assertion.

#	Invariant	Assertion
1	Every element reaches a root by following parent finitely.	No cycles other than the root self-loops. parent is a forest, never a ring.
2	A root is exactly an i with parent[i] == i.	There is no separate "is root" flag to fall out of sync.
3	count equals the number of roots.	count == sum(1 for i in range(n) if parent[i] == i)
4	The size values over all roots sum to n.	sum(size[i] for i in roots) == n
5	Groups only ever merge; they never split, shrink, or reorder.	count is non-increasing over the lifetime of the structure.

Invariant 5 is the one with teeth. It is not an implementation detail you could engineer around - it is the deal the structure makes in exchange for its speed, and the next section is entirely about what it costs you.

5. What DSU refuses to do

Knowing the limits is what makes the recognition reliable: if a problem needs any row of this table, plain DSU is the wrong tool, and reaching for it will produce code that looks right and is quietly wrong.

You want	Why plain DSU cannot
	What to do instead
Split a group / delete an edge	Merging overwrote the boundary between the two old groups. Nothing recorded where it was.
	Process the events in reverse time so deletions become insertions, or use a rollback DSU.
List the members of a group	Parents point up only; a root has no list of its children.
	One O(n) pass at the end, bucketing i under find(i). Cheap once, wasteful per query.
The path between two elements	The forest is not the input graph (see the gotcha above), and the facts were discarded.
	BFS or DFS on the actual graph. DSU can tell you a path exists; only a traversal can hand you one.
Distance between two elements	Same reason. Depth in the forest is an artifact of merge order.
	BFS for unweighted, Dijkstra for weighted - see Shortest Paths.
Directed reachability	Merging is symmetric: absorbing a -> b also asserts b -> a.
	SCC (Tarjan/Kosaraju) - see MST & SCC. DSU on a digraph silently computes weak connectivity.

⚠

DSU on a directed graph answers the wrong question

Union is symmetric, so DSU cannot see direction. Feed it the edges of a directed graph and it computes weakly connected components - the answer you would get by erasing every arrowhead. That is a correct answer to a different question, so nothing errors and the tests on small symmetric inputs pass. If the problem says "can a reach b" about a digraph, you need SCCs, not DSU.

6. The words

Five terms get used loosely and mean five different things. rank in particular is the one people expect to be the height and are then surprised by.

Word	Means
	The trap
Representative / root / leader	the unique element of a group with parent[i] == i
	Which element is the representative is arbitrary and changes over time. Never cache a find result across a union, and never expose it as a stable id.
Depth of an element	how many parent hops from it to its root
	This is the cost of one uncompressed find. It is a property of an element, not of the group.
Height of a tree	the maximum depth over the elements in it
	What union-by-rank is actually trying to hold down.
Rank of a root	an upper bound on the height, maintained cheaply
	Rank is not height. Path compression shortens trees without ever decrementing a rank, so rank drifts above the true height - deliberately. It stays a valid bound, which is all the proof needs.
Size of a root	the number of elements in its tree
	Unlike rank, this one is exact, and it is the value problems actually ask about ("largest component").

Mnemonic

Rank is a promise, size is a fact. size you can print in an answer; rank exists only to decide which of two roots wins a merge, and its staleness after compression is harmless by design.

7. Why not just relabel everything?

The obvious alternative: give every element a group id in an array, and on merge, sweep the array rewriting one id to the other. same(a, b) becomes an O(1) array read, which beats DSU.

It is a real technique - "quick find" - and it is worth understanding because it is the thing DSU is trading against.

Approach	same(a, b)	union(a, b)	n unions cost
Quick find - relabel on merge	O(1)	O(n) sweep	O(n^2)
Quick union - parent pointers, no balancing	O(n) worst case	O(n) worst case	O(n^2)
DSU - parent pointers, compression + rank	O(a(n))	O(a(n))	effectively O(n)

Quick find is genuinely the right choice when there are very few merges and an enormous number of queries, and it does have one property DSU lacks: the label is a stable, directly comparable group id. It loses the moment merges are frequent, which is the case every interview problem is built on. The rest of these pages are about the third row.

Mnemonic

Quick find pays on the way in; DSU pays on the way out. Quick find does the work when a fact arrives so queries are free; DSU does almost nothing when a fact arrives and amortises the rest across the queries. When facts and queries are interleaved - which is the shape of nearly every problem - the second deal is enormously better.

Next: Find & Union - the two operations, the two optimizations that make them fast, and a sandbox for turning each optimization off and watching the damage.