Source: CS 225 Slide Deck, UIUC
Tags: disjoint sets, union-find, find, union, UpTree, equivalence relation, representative element, path compression, union by rank, union by size, CS 225, data structures
Difficulty: Intermediate Prerequisites: Arrays, basic tree concepts, equivalence relations.
Disjoint sets track which elements belong to the same group when those groups can merge over time but never split. This comes up any time you need to answer "are these two things connected?" efficiently: network connectivity, Kruskal's minimum spanning tree algorithm, image segmentation, and equivalence-class problems. You should be comfortable with arrays and basic tree traversal before diving in.
A disjoint set (union-find) data structure maintains a collection of non-overlapping sets, each identified by a representative element. It supports two main operations, find (which set does this element belong to?) and union (merge two sets into one), and clever optimisations bring both operations down to nearly O(1) amortised time.
Disjoint sets
A collection of sets where no element belongs to more than one set. Formally, for any two sets s_i and s_j in the collection, s_i ∩ s_j = ∅. In simple terms, every element has exactly one home, and no home is shared between groups.
Representative element (canonical element)
A single designated member of each set that serves as the set's identity. When you call find on any element, you get back its set's representative. Think of it as: the "name tag" for the whole group.
find(k)
Returns the representative element of the set containing element k. Two elements are in the same set if and only if find(a) == find(b).
union(k1, k2)
Merges the set containing k1 with the set containing k2 into a single set. After a union, all elements from both original sets share the same representative.
makeSets(n)
Initialises n singleton sets, one per element. Each element starts as its own representative.
UpTree
The tree-based representation used in Implementation #2. Each node points to its parent. The root of each tree is the representative element for that set, and it points to itself (or stores a sentinel value like -1).
Equivalence relation
A relation R on a set that is reflexive (a R a), symmetric (a R b implies b R a), and transitive (a R b and b R c implies a R c). Disjoint sets model equivalence classes under such a relation.
The Disjoint Sets ADT maintains a collection S = {s₀, s₁, ..., s_k} with three operations:
void makeSets(int number) – create number singleton sets
int find(int k) – return the representative of the set containing k
void union(int k1, int k2) – merge the sets containing k1 and k2
The core question the structure answers: "Are elements a and b in the same set?" You check by comparing find(a) == find(b).
Use an array where the index is the element and the stored value is the set's identity (e.g. the representative element's index).
find(k): return array[k]. This is O(1).
union(k1, k2): must scan the entire array and update every element that shares k2's representative to now hold k1's representative. This is O(n).
This approach gives fast find but slow union. For m operations on n elements, the worst case is O(mn).
Each element is a node in a forest of trees. Each node stores the index of its parent. Roots store -1 (indicating they are the representative).
Initial state for 4 elements:
Index | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
Value | -1 | -1 | -1 | -1 |
Every element is its own root, so every element is its own representative.
find(k):
Follow parent pointers from k upward until you reach a root (a node whose value is -1). Return that root's index. Worst case: O(n) if the tree degenerates into a linked list. Typical case with optimisations: nearly O(1).
union(k1, k2):
Find the root of k1's tree.
Find the root of k2's tree.
Make one root point to the other.
This is O(1) beyond the cost of the two finds.
Union by rank (or union by size)
When merging two trees, attach the shorter (or smaller) tree under the root of the taller (or larger) tree. This keeps trees balanced and guarantees a maximum height of O(log n).
Union by rank: track the height of each tree; attach the shorter tree under the taller one. If heights are equal, pick either and increment the new root's rank by one.
Union by size: track the number of elements in each tree; attach the smaller tree under the larger one.
Path compression
During find, make every node on the path from k to the root point directly to the root. This flattens the tree for future operations.
int find(int k) {
if (array[k] < 0) return k;
array[k] = find(array[k]); // path compression
return array[k];
}
Combined performance:
With both union by rank and path compression, any sequence of m find/union operations on n elements runs in O(m · α(n)) time, where α is the inverse Ackermann function. For all practical purposes, α(n) ≤ 4, so each operation is effectively O(1) amortised.
Simple array: find is O(1), union is O(n)
Naive UpTree (no optimisations): find is O(n) worst case, union is O(n) worst case
UpTree with union by rank only: find is O(log n), union is O(log n)
UpTree with union by rank + path compression: amortised O(α(n)) per operation, which is effectively constant
α(n) = inverse Ackermann function; α(n) ≤ 4 for any n up to approximately 2^(2^(2^(2^16)))
Kruskal's minimum spanning tree algorithm uses union-find to check whether adding an edge would create a cycle: if two vertices share the same representative, they are already connected. Network connectivity problems (is server A reachable from server B?) map directly onto disjoint sets. Image processing uses union-find for connected-component labelling, grouping adjacent pixels of similar colour into regions.
Students often think find always returns the element itself. It returns the representative of the element's set, which may be a completely different element.
A common mistake is forgetting that union by rank tracks tree height, not tree size. They are different optimisations that both help, but they are not interchangeable in proofs.
Students sometimes assume path compression changes the logical grouping of elements. It does not. It only restructures the tree to make future finds faster. The sets themselves remain identical.
It is easy to confuse the simple array implementation (where union is O(n) and find is O(1)) with the UpTree implementation (where naive find is O(n) and union is O(1) after finding roots). They have opposite bottlenecks.
⚠️ Be able to trace find and union operations on an UpTree array, showing the array state after each step, especially with path compression.
⚠️ Know the running times for both implementations and both optimisations. The inverse Ackermann function and its practical meaning (effectively constant) are commonly tested.
⚠️ Understand why union by rank alone gives O(log n) per find, and how adding path compression drops it to amortised O(α(n)).
⚠️ Disjoint sets appear in Kruskal's algorithm, so expect questions that combine these two topics.
True or False: In a disjoint set, an element can belong to more than one set.
Fill in the blank: Path compression makes every node on the find path point directly to the ______.
True or False: Union by rank attaches the taller tree under the shorter tree.
True or False: With union by rank and path compression, each operation takes O(log n) amortised time.
Fill in the blank: In the simple array implementation, find is O() and union is O().
Answers: 1. False. 2. Root. 3. False (the shorter tree is attached under the taller). 4. False (it is O(α(n)), effectively constant). 5. O(1) and O(n).
Q: Starting from makeSets(8), perform union(1, 0), union(4, 0), union(7, 2), union(5, 3), union(6, 3). Show the UpTree array after all operations (no optimisations).
A: After union(1,0): 1 points to 0. Array: [-1, 0, -1, -1, -1, -1, -1, -1]. After union(4,0): 4 points to 0. Array: [-1, 0, -1, -1, 0, -1, -1, -1]. After union(7,2): 7 points to 2. Array: [-1, 0, -1, -1, 0, -1, -1, 2]. After union(5,3): 5 points to 3. Array: [-1, 0, -1, -1, 0, 3, -1, 2]. After union(6,3): 6 points to 3. Array: [-1, 0, -1, -1, 0, 3, 3, 2].
Q: What is the purpose of the -1 sentinel value in the UpTree array?
A: A -1 at index i indicates that element i is a root node (the representative of its set). Any non-negative value at index i means element i's parent is the element at that index. When find reaches an index storing -1, it has found the representative.
Q: Explain why path compression does not change which elements belong to which set.
A: Path compression only changes the internal tree structure by redirecting parent pointers to point directly at the root. Every element still has the same root (representative) after compression, so set membership is unchanged. The operation is purely a performance optimisation that flattens the tree for faster future queries.
Q: In Kruskal's algorithm, how are disjoint sets used?
A: Kruskal's algorithm processes edges in order of increasing weight. Before adding an edge (u, v), it calls find(u) and find(v). If they return the same representative, u and v are already connected, so adding the edge would create a cycle, and it is skipped. If the representatives differ, the edge is added to the MST and union(u, v) merges the two components.
Disjoint sets connect directly to Kruskal's minimum spanning tree algorithm (graph theory, covered later in CS 225). The equivalence-relation foundation ties back to discrete mathematics. The amortised analysis involving the inverse Ackermann function is a landmark result in algorithm analysis and connects to the broader topic of amortised complexity studied alongside hash tables and dynamic arrays.
disjoint sets, union-find, union by rank, union by size, path compression, UpTree, up-tree, equivalence class, representative element, canonical element, find operation, union operation, makeSets, inverse Ackermann function, Kruskal's algorithm, connected components, CS 225, UIUC data structures, forest of trees