← Union-Find & MST · guided lesson
Union-Find & Minimum Spanning Trees
the story
Union-Find (Disjoint Set Union)
Every tool here exists because something was too slow or broke without it. Here is what.
In 1964 Galler and Fischer published a three-page CACM paper on a compiler chore: FORTRAN's EQUIVALENCE statements say which variables share memory, and the compiler must group them. Their idea was to store each group as a tree, finding every group in one scan of the declarations — cutting computation time by 40% compared with the method published before it. Why it is so fast took another decade: Hopcroft and Ullman (1973) proved an O(log* n) bound, and Tarjan (1975) pinned it to the inverse Ackermann function α(n). In 1989 Fredman and Saks proved that, in the cell-probe model, no structure can beat α(n) amortized per operation.
the problem it solved
Grouping things that are declared equal pair by pair, and answering "same group?" without re-scanning everything.
why it matters: without it
Every "are these connected yet?" question would mean a fresh BFS/DFS over the whole graph — fine once, hopeless after each of millions of updates.
sources: Galler & Fischer — An improved equivalence algorithm (CACM, 1964) ↗ · Hopcroft & Ullman — Set Merging Algorithms (SIAM J. Computing, 1973) ↗ · Tarjan — Efficiency of a Good But Not Linear Set Union Algorithm (JACM, 1975) ↗ · Fredman & Saks — The cell probe complexity of dynamic data structures (STOC, 1989) ↗
also in this chapter: Minimum spanning tree (and the cut property) · Kruskal's algorithm · Prim's algorithm (Jarník–Prim)
the idea
The idea in 30 seconds
Union-Find (a Disjoint Set Union, DSU) keeps elements in groups and answers two questions fast: which group is x in? and merge these two groups.
Each group is a small tree stored in a parent[] array; the root is the group's name. Two tricks — union by size and path compression — keep the trees almost flat.
A minimum spanning tree (MST) connects every node of a weighted graph with the least total weight. Kruskal = cheapest edges first, skipping any that close a cycle (DSU spots them). Prim = grow one tree with a min-heap.
picture this
Your phone's contacts app merging duplicates. Every contact card points to a "main" card, and the main card is the person. "Same person?" = follow both cards to their main cards and compare. Merging two people = one main card starts pointing at the other. Path compression = after one long lookup, every card you passed now points straight at the main card, so the next lookup is one hop.
watch it
Union-Find forest — union by size + path compression
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
Union-Find forest — union by size + path compression
Top: the forest (arrows point to parent). Below: the same thing as `parent[]` and `size[]`. Watch nodes re-point at their root during find.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
watch it
Cycle detection — the edge whose ends are already connected
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
Cycle detection — the edge whose ends are already connected
Edges arrive one at a time. Same root = there is already a path, so this edge closes a cycle (red).
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
key idea 1 of 8
Read it once. Say it out loud once. Bas.
parent[i] points one step up; a root has parent[r] == r. Two elements are in the same set exactly when they have the same root.
key idea 2 of 8
Read it once. Say it out loud once. Bas.
find(x) walks up to the root. union(a, b) finds both roots and hangs one under the other. Everything else is built from these two.
key idea 3 of 8
Read it once. Say it out loud once. Bas.
Union by size (or rank): hang the smaller tree under the bigger root, so height stays ≤ log₂ n. Path compression: during find, re-point every visited node straight at the root.
key idea 4 of 8
Read it once. Say it out loud once. Bas.
With both tricks, any sequence of m operations costs O(m·α(n)). α is the inverse Ackermann function — α(n) ≤ 4 for any n you will ever meet, so treat each operation as amortized constant time.
key idea 5 of 8
Read it once. Say it out loud once. Bas.
Counting components: start with count = n; every union that actually merges two sets does count--. Cycle detection (undirected): an edge whose two ends already share a root closes a cycle.
key idea 6 of 8
Read it once. Say it out loud once. Bas.
Cut property — the reason greedy MST works: split the nodes into any two groups; the cheapest edge crossing between them is safe to put in some MST.
key idea 7 of 8
Read it once. Say it out loud once. Bas.
Kruskal: sort edges (O(E log E)), then take each edge whose ends are in different DSU sets. Prim: start anywhere, repeatedly add the cheapest edge leaving the tree (PriorityQueue, O(E log V)); an O(V²) array version wins on dense/complete graphs.
key idea 8 of 8
Read it once. Say it out loud once. Bas.
A spanning tree of n nodes has exactly n − 1 edges. Fewer usable edges means the graph is disconnected — there is no spanning tree.
spot the pattern
When you see this, think this
"Groups", "connected", "same component", "friends of friends", "merge accounts"
Union-Find (or DFS) over the connection relation
Edges/connections are given as a list and arrive over time
Union-Find: union each edge, track count or detect the redundant one
"Which edge creates a cycle?" or "is this a valid tree?" in an undirected graph
The first union whose ends share a root; a tree also needs exactly n − 1 edges
Equalities and inequalities (
a == b,b != c), or "is this assignment consistent?"Union all equalities, then check every inequality spans two sets
+3 more signals on the chapter page
watch out
A trap or two
Many wrong answers in interviews come from small slips like these, not from the hard part.
- Comparing
parent[a] == parent[b]instead offind(a) == find(b)— parents are not roots. - Writing
parent[a] = bin union instead ofparent[find(a)] = find(b)— you re-parent a node, not its whole set, and break other members.
quick check
One question. No pressure.
parent = [0, 0, 1, 3, 3]. What does find(2) return, and what is parent[2] after path compression?
now try
Your first real problem
You know enough to try this one. Stuck? Use the hints; that is what they are for.
Number of Provinces
open the problem →recall
Flip a few cards
Answer in your head first, then flip. Grade yourself honestly; the schedule brings back what you forget.
What two operations does Union-Find support, and what does a root mean?
Question 1: What two operations does Union-Find support, and what does a root mean?
done
Lesson complete
Chalo, that is the core. The full chapter has the rest: cost tables, Java details and more problems.