Two support tickets: account 41 and account 902 both just hit the fraud queue. They never transferred money. They never shared an IP on the same day. They did both log in from a device that a third account used last week. Are they in the same cluster?
If you build an adjacency list of every account–device–account edge and walk from 41, you will get the right answer. You will also store a graph you never traverse except to ask same component? Union-Find (disjoint-set) keeps a parent pointer per element and answers that question without the neighbor list.
The series hub owns amortized vs worst-case and the rest of the glossary. This post is the layout: a parent array, find, union, and the two tweaks that keep those calls nearly constant.
The parent array is the whole structure
Give every element an integer id in 0 … n-1. Store one array: parent[i] is the id of i’s parent. A root points at itself. The forest of those trees is the partition into disjoint sets.
int[] parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i; // each element starts in its own set
}Five accounts, no links yet: five trees of height zero. After you record that 0 shares a device with 1, and 1 with 2, the array might look like this:
id 0 1 2 3 4
parent 1 2 2 3 40 and 1 hang under 2. 3 and 4 are still their own components. There is no edge list. There is no “neighbors of 0.” There is only “who is my parent, and who is the root?”
Note: Mapping real keys (account ids, hostnames) onto 0 … n-1 is your job — a HashMap<String, Integer> in front of this array. Union-Find itself is indexed storage.
Find: walk to the root
find(x) follows parent until it hits a node that points at itself. Two elements are in the same set exactly when they share a root.
int find(int[] parent, int x) {
while (parent[x] != x) {
x = parent[x];
}
return x;
}
boolean connected(int[] parent, int a, int b) {
return find(parent, a) == find(parent, b);
}On the array above, find(0) walks 0 → 1 → 2 and returns 2. find(2) is already 2. connected(0, 2) is true; connected(0, 3) is false.
A naive find is honest and slow if unions always attach in a line. A chain of n nodes makes find(leaf) walk n hops. The structure still answers the question. It just stopped being cheaper than scanning a list.
Union: attach one root to the other
To merge two sets, find both roots and hang one under the other. If they already share a root, there is nothing to do — that “no-op” is how you detect that an undirected edge would close a cycle.
void union(int[] parent, int a, int b) {
int ra = find(parent, a);
int rb = find(parent, b);
if (ra == rb) {
return; // already the same component
}
parent[ra] = rb;
}Always attaching ra under rb is enough for correctness. It is also how you grow a stick: union 0-1, then 1-2, then 2-3, always linking the new root onto the old chain. Correct union without a height policy degrades to a linked list. Flatten on find; attach the shorter tree under the taller one on union.
Path compression: flatten on the way up
After find(x) knows the root, every node it touched can point straight there. The next find on that path is one hop.
int find(int[] parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}The recursive assignment is the compression. A two-pass loop (walk up, then walk again writing the root) does the same work if you would rather not recurse.
Start from a chain 0 → 1 → 2 → 3. After find(0) with compression:
id 0 1 2 3
parent 3 3 3 3find mutated the tree. That is allowed: the partition did not change — only the shape that represents it. Same roots, shorter paths.
Note: Compression assumes a single-threaded owner of the array. Concurrent finds that rewrite parent without a lock will tear the forest. Treat this as a mutable structure you do not share across threads, or wrap the whole instance.
Union by rank (or size): keep trees shallow
Path compression repairs trees after the fact. Union by rank (or by size) stops you from building a tall tree in the first place.
Keep a parallel array. Rank is an upper bound on height: a singleton has rank 0. When you attach equal-rank roots, the new root’s rank becomes old + 1. When ranks differ, hang the smaller rank under the larger and leave ranks alone. Size is the component’s element count: hang the smaller tree under the larger and add the sizes.
void union(int[] parent, int[] rank, int a, int b) {
int ra = find(parent, a);
int rb = find(parent, b);
if (ra == rb) {
return;
}
if (rank[ra] < rank[rb]) {
parent[ra] = rb;
} else if (rank[ra] > rank[rb]) {
parent[rb] = ra;
} else {
parent[rb] = ra;
rank[ra]++;
}
}Either policy is enough. Combining one of them with path compression is the version you ship. Amortized cost per find / union is inverse-Ackermann in n — for every n you will ever store, treat those calls as nearly O(1). That is amortized in the hub sense: cheap on a long sequence, not a promise that the next hop cannot walk a short path.
| Operation | Naive (no heuristics) | Rank/size + path compression |
|---|---|---|
find | O(n) worst chain | amortized nearly O(1) |
union | O(n) (dominated by find) | amortized nearly O(1) |
connected | two finds | two finds |
| Extra space | parent[n] | parent[n] + rank[n] or size[n] |
A Java sketch you can run
One class: path compression, union by rank, a component counter. union returns whether a merge actually happened.
public final class UnionFind {
private final int[] parent;
private final int[] rank;
private int components;
public UnionFind(int n) {
parent = new int[n];
rank = new int[n];
components = n;
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
public boolean union(int a, int b) {
int ra = find(a);
int rb = find(b);
if (ra == rb) {
return false;
}
if (rank[ra] < rank[rb]) {
parent[ra] = rb;
} else if (rank[ra] > rank[rb]) {
parent[rb] = ra;
} else {
parent[rb] = ra;
rank[ra]++;
}
components--;
return true;
}
public boolean connected(int a, int b) {
return find(a) == find(b);
}
public int components() {
return components;
}
}Four device-sharing events and two queries:
UnionFind accounts = new UnionFind(5);
accounts.union(0, 1);
accounts.union(1, 2);
accounts.union(3, 4);
System.out.println(accounts.connected(0, 2)); // true
System.out.println(accounts.connected(0, 3)); // false
System.out.println(accounts.components()); // 2true
false
2There is no java.util.UnionFind. This is a structure you write (or pull from a library) because the JDK collections do not ship it. The arrays are the layout; the class is just a fence around them.
Jobs: components, and Kruskal as a consumer
The fraud opener is the usual job: a stream of “these two belong together” events, and a membership query. Friend groups, failed-link domains in a network, and “how many islands after these merges” are the same shape. You need the count of roots, or a yes/no on two ids. You do not need the walk between them.
Cycle detection on an undirected edge set is the no-op branch: if union returns false, that edge sits inside one component already.
Kruskal’s minimum spanning tree algorithm is a famous user, not a reason to study MST here. It sorts edges by weight, then asks Union-Find whether the endpoints are already in the same tree; if not, it accepts the edge and unions. The algorithm owns the sort. Union-Find only answers would this merge two components?
When not to use Union-Find
Skip it when the question is not membership:
- You need neighbors, degrees, or a walk — shortest path, BFS layers, “who is adjacent to this node.” Those need an adjacency list or matrix. Union-Find threw the edges away after merging.
- Directed reachability — parent pointers are not “can I get from
utovin a digraph.” Connectivity here is symmetric. - Un-union — splitting a component back apart is not a cheap inverse of
union. If links disappear as often as they appear, this is the wrong layout. - List everyone in this cluster, often — you can scan
parentand group by root (O(n)per dump), but if that dump is the hot path, store the members explicitly.
Union-Find is cheap because it forgets the graph. If you still need the graph, build the graph.
Cheat sheet
Layout: parent[i] = parent of i; root has parent[i] == i
find(x): walk to root (compress: parent[x] = root)
union(a,b): find both; attach one root to the other
Shallow: union by rank (height bound) or by size (smaller under larger)
connected: find(a) == find(b)
Cost: with both heuristics, amortized nearly O(1)
Space: parent[n] + rank[n] or size[n]
JDK: none — you write the arrays
Good: components, undirected cycle check, Kruskal's membership test
Avoid: neighbors, shortest path, directed reachability, un-unionDo:
- Index elements
0 … n-1; map real keys in a table you own. - Ship path compression and rank or size. Either heuristic alone is better than neither; both is the default.
- Treat
unionreturningfalseas “already connected” — that is the cycle signal on undirected edges.
Don’t:
- Build an adjacency list only to ask “same component?”
- Union without a height/size policy and call the result
O(1). - Expect this structure to answer “the path from
atob” or “the neighbors ofx.”
Wrap-up
Union-Find stores a partition, not a graph. A parent array plus find and union grows connected components from a stream of links; path compression and union by rank (or size) keep those calls nearly constant. The jobs are membership, component counts, and algorithms that only need that test — Kruskal included, as a consumer. If you need edges, neighbors, or a walk, you need a graph. If you only need “are these two already together?” you do not. Glossary (ADT vs implementation, amortized vs worst-case) lives on the Data Structures Roadmap.