Difficulty: Intermediate | Prerequisites: Trees, arrays, basic amortised analysis concepts.
Disjoint sets (also called union-find) track a collection of non-overlapping groups and let you merge them or check membership extremely quickly. This data structure appears wherever you need to detect connected components, and it is the engine behind Kruskal's minimum spanning tree algorithm. If you are comfortable with tree representations stored in arrays, you will find this straightforward.
Disjoint sets let you partition elements into groups, merge two groups together, and check whether two elements belong to the same group, all in nearly constant time. The two key optimisations, path compression and union by rank/size, bring the amortised cost per operation down to O(α(n)), where α is the inverse Ackermann function, which is effectively constant for any input size you will ever encounter.
Disjoint set (union-find)
A data structure that maintains a collection of non-overlapping (disjoint) sets and supports two primary operations: union (merge two sets) and find (determine which set an element belongs to). Think of it as a way to keep track of groups that can merge but never split.
Find
The operation that returns the representative (root) of the set containing a given element. You follow parent pointers up the tree until you reach a node that points to itself. In simple terms, you are asking: "Who is the leader of this element's group?"
Union
The operation that merges two sets into one by connecting the root of one tree to the root of the other. After a union, both sets share the same representative.
Path compression
An optimisation applied during find. After finding the root, every node along the path is re-pointed directly to the root. This flattens the tree so future finds are faster. Think of it as: once you know the boss, skip all the middle managers next time.
Union by rank (height)
A strategy for union that attaches the shorter tree under the root of the taller tree. This keeps the combined tree shallow. "Rank" here is an upper bound on the tree's height.
Union by size
A strategy for union that attaches the smaller set (fewer elements) under the root of the larger set. The effect is similar to union by rank: it prevents the tree from getting tall and stringy.
Inverse Ackermann function, α(n)
A function that grows extraordinarily slowly. For all practical input sizes (up to roughly 2^65536), α(n) is at most 4. When people say disjoint-set operations are "effectively O(1)," this is what they mean.
Forest of trees
The internal representation of disjoint sets: each set is a tree, and the collection of all sets is a forest. Typically stored in a single array where each element holds a pointer to its parent (the root points to itself).
Every element starts as its own set (a singleton). In the array representation, each element's parent pointer points to itself
The collection of all sets forms a forest of up-trees: each tree is one set, and its root is the representative of that set
Initial state for n elements: an array of size n where parent[i] = i for all i
Basic find: follow parent pointers from a given element until you reach a node whose parent is itself (the root). Return the root
Path compression: after finding the root, make every node on the path point directly to the root. This is typically done during the recursive unwinding
The result is that subsequent finds on any of those nodes are nearly instant
Pseudocode pattern: if parent[x] is not x, set parent[x] = find(parent[x]), then return parent[x]
Union by size: Maintain a size count for each root. When merging two sets, attach the root of the smaller set under the root of the larger set. Update the size of the new root
Union by rank (height): Maintain a rank (upper bound on height) for each root. Attach the root with lower rank under the root with higher rank. If ranks are equal, pick one and increment its rank
Both strategies prevent the tree from degenerating into a long chain, which would make find slow
Either strategy combined with path compression yields amortised O(α(n)) per operation
Operation | Without optimisations | With path compression + union by rank/size |
|---|---|---|
Find | O(n) worst case | O(α(n)) amortised |
Union | O(n) worst case | O(α(n)) amortised |
Make set | O(1) | O(1) |
The unoptimised case degenerates when unions consistently produce a long chain (like a linked list). Path compression and smart union strategies keep the trees nearly flat.
Disjoint sets power Kruskal's minimum spanning tree algorithm: as you process edges in weight order, union-find tells you instantly whether adding an edge would create a cycle. Network engineers use the same idea to detect connected components in large networks, and image processing algorithms use it to label connected regions of pixels.
Students often forget that path compression happens during find, not during union. Union just connects two roots; find is where the tree gets flattened
Students sometimes think union by rank and union by size are the same thing. They are similar in effect but track different quantities. Rank is an upper bound on height; size is the element count. After path compression, rank may overestimate the true height
Students assume α(n) is some exotic complexity class they need to worry about. For exam purposes, treat O(α(n)) as effectively constant. The key point is that both optimisations together make the operations nearly free
Students forget that without both optimisations, the worst case is O(n) per find. Path compression alone or union by rank alone each improve things, but the combination is what delivers O(α(n))
Expect a question asking you to trace a sequence of union and find operations, showing the tree structure and the effect of path compression after each find
Know the difference between union by rank and union by size, and be ready to explain why both keep trees shallow
Be prepared to state the amortised runtime with both optimisations and to name the inverse Ackermann function
Kruskal's algorithm is the most common application question: you may be asked how union-find is used to check for cycles
True or false: Path compression changes the tree structure during a union operation.
Fill in the blank: With path compression and union by rank, find runs in amortised O(____) time.
True or false: Union by rank always produces a shorter tree than union by size.
Fill in the blank: In the initial state, every element's parent pointer points to ____.
True or false: α(n) exceeds 5 for inputs of size 10^100.
Answers: 1. False (path compression happens during find). 2. α(n). 3. False (both strategies produce similarly shallow trees; neither is strictly better). 4. Itself. 5. False (α(n) is at most 4 for any practically conceivable input).
Q: Starting with elements {0, 1, 2, 3, 4}, perform union(0,1), union(2,3), union(1,3) using union by rank. Draw the resulting forest.
A: After union(0,1): tree rooted at 0, with 1 as its child (or vice versa, both rank 0, so pick 0 as root, set rank to 1). After union(2,3): tree rooted at 2, with 3 as child (rank 1). After union(1,3): find(1) returns 0, find(3) returns 2. Both roots have rank 1, so pick one (say 0) as the new root. Attach 2 under 0. Result: tree rooted at 0 with children 1 and 2, and 2 has child 3. Element 4 remains a singleton.
Q: Explain what happens to the tree when you call find(3) with path compression, given the chain 3 → 2 → 1 → 0 (0 is root).
A: find(3) follows the chain to the root (0). On the way back, path compression re-points every node on the path directly to 0. After the call, parent[3] = 0, parent[2] = 0, and parent[1] = 0. The tree is now a star with 0 at the centre.
Q: Why does Kruskal's algorithm need a disjoint-set data structure?
A: Kruskal's processes edges in order of increasing weight. Before adding an edge (u, v), it needs to check whether u and v are already in the same connected component (which would create a cycle). find(u) and find(v) answer that question in near-constant time, and union(u, v) merges the two components when the edge is accepted.
This connects directly to graph algorithms: Kruskal's MST algorithm is the classic use case, and detecting connected components in an undirected graph is another. It also connects to heaps, since Prim's MST algorithm uses a priority queue (heap) rather than union-find, giving you two different approaches to the same problem.
disjoint set, union-find, union by rank, union by size, path compression, inverse Ackermann, forest of up-trees, connected components, Kruskal's algorithm, cycle detection, make set, find set, amortised analysis, DSA exam 4, data structures UIUC