Suppose connections arrive one at a time between eight computers. After connecting 0 to 1 and 1 to 2, we should recognize that 0 and 2 belong to the same connected group, even if no direct connection joins them. Listing every member of every group after each new connection would do more work than this question requires. A disjoint-set structure records enough information to recognize and merge groups efficiently.
The central distinction is between which elements belong together and which pointers represent that fact. A query may rearrange those pointers without changing any group. Conversely, a successful union changes the groups even though it may alter only one parent pointer. Keeping both levels in view makes the algorithms easier to prove and debug.
Start with a partition and its operations
Definition 1.1.1
(Partition and disjoint-set operations)
A partition of a universe is a collection of nonempty, pairwise disjoint subsets whose union is . Every element therefore belongs to exactly one subset, called its set or component.
For , initialize one singleton set per element. find(x) returns a representative of the set containing . unite(x,y) merges their two sets if they differ. Two elements are connected in this abstract sense exactly when their current representatives are equal.
For example, is a partition of . It is not a list of graph edges: it records the groups obtained after taking connectivity into account. Within one component, the relation “belongs to the same set” is reflexive, symmetric and transitive.
| Operation | Abstract result | Can it change the partition? |
|---|---|---|
find(x) | The current representative of 's set | No |
connected(x,y) | Whether the representatives agree | No |
unite(x,y) | Whether two distinct sets were merged | Yes, precisely when the returned result is true |
sizeOf(x) | The number of elements in 's set | No |
The representative is an implementation choice, not a permanent name for an application object. A later union can change it. In particular, it need not be the smallest element of the set.
Concept lensStructural
Unions as joins of partitions
Order the partitions of by refinement: when every block of lies inside a block of . Then unite(x,y) replaces by the smallest partition above in which and share a block. Hence the partition after a sequence of unions depends only on which pairs were united, not on their order or repetition, although the parent forest does. For example, uniting gives in either order, with parent arrays [0,0,0] and [1,1,1] under the union-by-size rule used below, which keeps the lower-labeled root on a tie.
A parent forest represents the partition
Store an array parent. A root has parent[r] == r; any other element points toward its component's root. Apart from these root self-pointers, the parent edges form trees with no cycles. Following parents from any element must reach exactly one root. Two elements are in the same component if and only if their paths reach the same root.
At a root, size[r] records the size of the whole component, not the number of direct children and not the size of one visible branch. Nonroot size entries will not be used as component sizes. Initially, parent[x] = x, size[x] = 1, and the number of components is .
Worked example 1.1.2
(Build a forest without flattening every branch)
Use eight elements. Always attach the smaller component beneath the larger one; if their sizes tie, keep the lower-labeled root. Starting from singleton sets, perform:
| Union | Surviving root | Size of the merged component | Components remaining |
|---|---|---|---|
unite(0,1) | |||
unite(2,3) | |||
unite(0,2) | |||
unite(4,5) | |||
unite(6,7) | |||
unite(4,6) | |||
unite(0,4) |
Each call links roots. It does not automatically redirect every other node to the surviving root. The resulting parents are:
| Element | ||||||||
|---|---|---|---|---|---|---|---|---|
| Parent |
The path from 7 is , while the path from 3 is . Different path lengths do not indicate different components: both reach 0. Only root 0 now carries the component size 8.
Path compression changes the representation, not membership
A first pass of find(7) follows three parent edges to discover root 0. Full path compression then redirects the visited elements to that root. Parent entries 7 and 6 change to 0; entry 4 already equals 0, so its value does not change. All other entries stay as they were. A second find(7) follows only the edge .
For these counts, a discovery hop means following one parent edge during the first pass toward the root. Exclude both the root's self-pointer and the second, compression pass; that pass also traverses the old route in the implementation below. Count a changed parent entry only when its value differs afterwards. Under these conventions, the first query takes three discovery hops and changes two entries; the second takes one discovery hop and changes none. These counts describe this prepared example, not a constant worst-case bound for every query.
Proposition 1.1.3
(Path compression preserves the partition)
Let find(x) redirect the parent of every visited element to the root that it discovers. After the redirection every element has the same root as before, so the partition represented by the parent forest, and the counters at the roots, are unchanged.
Proof
(Why compression preserves every represented set)
Suppose a visited element already reaches root . Replacing its parent by preserves that destination. It cannot create a nontrivial cycle: is a root, so its path never leads back through a distinct descendant.
Any other element whose path reaches will now take a shorter continuation to the same root . Paths that never reach a rewritten element remain unchanged. Thus every element has the same root before and after compression, and equality of roots represents exactly the same partition. Root size counters remain correct because no component gained or lost a member.
This is why find can modify the parent array while remaining a query at the abstract level. It improves the representation without merging or splitting sets.
Implement root linking and compression together
The following complete C++ example assumes and that every operation receives an existing label in . The class creates its singleton sets once; it supports merging, not deleting elements or separating components.
#include <iostream>
#include <numeric>
#include <utility>
#include <vector>
class DisjointSet {
std::vector<int> parent, size;
int components;
public:
explicit DisjointSet(int n) : parent(n), size(n, 1), components(n) {
std::iota(parent.begin(), parent.end(), 0);
}
int find(int x) {
int root = x;
while (parent[root] != root) root = parent[root];
while (parent[x] != x) {
int next = parent[x];
parent[x] = root;
x = next;
}
return root;
}
bool unite(int x, int y) {
int a = find(x), b = find(y);
if (a == b) return false;
if (size[a] < size[b] || (size[a] == size[b] && a > b)) {
std::swap(a, b);
}
parent[b] = a;
size[a] += size[b];
size[b] = 0;
--components;
return true;
}
bool connected(int x, int y) { return find(x) == find(y); }
int sizeOf(int x) { return size[find(x)]; }
int count() const { return components; }
};
int main() {
DisjointSet sets(8);
for (auto edge : std::vector<std::pair<int, int>>{
{0, 1}, {2, 3}, {0, 2}, {4, 5}, {6, 7}, {4, 6}, {0, 4}}) {
sets.unite(edge.first, edge.second);
}
std::cout << sets.find(7) << ' ' << sets.count() << ' '
<< sets.sizeOf(7) << '\n';
}
The output is 0 1 8: representative 0, one component, eight members. In find, save the old parent in next before overwriting it; otherwise the second pass would lose the original route. Assigning a parent that already equals root is harmless but is not a changed-entry event in the earlier count.
In unite, both a and b are roots before the size comparison. Linking distinct roots combines exactly their two trees and cannot create a cycle, because the roots belonged to different trees. Combining the sizes and reducing the component count records that one successful merge. Clearing size[b] marks its obsolete counter; only root entries are used by sizeOf.
If both finds return the same root, the method returns false and leaves the partition and component count unchanged. The finds may nevertheless have compressed paths before that decision. “No new union” does not mean “no parent entry was written.”
Worked example 1.1.4
(A redundant union still writes parent entries)
Start from the parent array [0,0,0,2,0,4,4,6] above and call unite(7,4). The call find(7) follows , three hops, and rewrites parent[7] and parent[6] to 0; parent[4] is already 0. The call find(4) takes one hop. Both roots are 0, so unite returns false, the number of components stays 1, and size[0] stays 8. Yet the array has become [0,0,0,2,0,4,0,0]. No merge occurred, but parent entries were written.
Common mistake
(Comparing parent entries instead of roots)
In [0,0,0,2,0,4,4,6] we have parent[3]=2 and parent[1]=0, which differ, yet 1 and 3 are in the same component. A connectivity test must compare find(1) and find(3), both of which equal 0.
Common mistake
(Reading a size counter at a nonroot element)
The implementation clears the counter of the root that gets linked: after unite(2,3) the entry size[3] is 0, although 3 lies in a component of 8 elements. A component size must be read as sizeOf(3), that is size[find(3)].
Counterexample mode
An arbitrary parent assignment can split an old set
Suppose parent = [0, 0, 1, 3]. It represents and . A faulty attempt to implement unite(2,3) assigns parent[2] = 3. The new roots now describe and . Element 2 has been detached from its old partners instead of merging the two complete sets.
Find roots 0 and 3 first, then link one root beneath the other. In the shown implementation, finding 2 first compresses its parent to 0; the size rule then links 3 beneath 0, giving [0, 0, 0, 0] and one set . The old members still reach the same root. A disjoint-set union merges classes; it must never split one merely because a nonroot element was supplied as an argument.
Prove the depth bound by doubling
Theorem 1.1.5
(Union by size bounds the depth)
Suppose every union attaches the root of the smaller component beneath the root of the other, with ties broken arbitrarily. Then in a universe of elements every element has depth at most , so each find takes time.
Proof
(Union by size limits how often a depth can increase)
First consider unions without path compression. An element's depth increases by one only when its component's root is attached to another root. If its component had size , the size rule attaches it to a component of size at least . Its new component therefore has size at least .
Starting from a singleton, after such depth increases the containing component has at least elements. Since the whole universe has elements,
for . Thus a root traversal takes time. Compression can only shorten paths, so it does not invalidate this upper bound. A find with two passes takes at most a constant multiple of the traversed path length; a union makes two such finds and a constant amount of additional work.
The eight-element construction reaches depth three at element 7 before compression, matching . Repeating a compressed query can be much cheaper. A sharper amortized analysis of many operations needs a further argument; it does not follow merely from observing a short second path.
Proof X-ray
Why union by size doubles the component
One inequality carries the proof: the tree whose root is attached is no larger than the tree receiving it, so the attached elements land in a component at least twice as big as before. It applies only to elements of the attached tree; elements of the receiving tree keep their depth. Compression enters through a single remark: it can only lower depths, so depth never exceeds the number of increases, even when some paths have already been shortened.
The rule cannot be dropped. If unite(x,y) always attached the root of 's set beneath the root of 's set, the calls unite(0,1), unite(1,2), , unite(n-2,n-1) would build the chain , and find(0) would traverse edges.
Initialization takes time and the two arrays take space. State the cost of the whole operation: linking known roots is constant work, while unite(x,y) must first find them.
Apply the abstraction to incremental connectivity
For a fixed set of vertices, start with no edges and singleton sets. Whenever an undirected edge arrives, call unite(u,v).
Theorem 1.1.6
(Union–find tracks incremental connectivity)
With this procedure, after every processed edge two vertices have equal representatives exactly when the edges processed so far connect them by a path.
Proof
(Each edge either joins two components or stays inside one)
Initially there are no such paths between distinct vertices. Adding an edge either joins two old connected components or stays inside one. The union operation makes exactly that same distinction, so the invariant is preserved after every insertion.
This proves that connected(u,v) answers the current connectivity question; it does not recover an actual graph path. Parent edges are implementation pointers and need not be input edges.
For a simple undirected graph, an edge whose endpoints are already connected would close a cycle with an existing path. This makes disjoint sets useful for Kruskal's cycle check: process edges in nondecreasing weight order and accept an edge when its endpoints lie in different sets. The data structure implements that test; the minimum-spanning-tree claim additionally needs the greedy cut argument, which is separate from the union–find invariant.
Worked example 1.1.7
(Accepting and rejecting edges one by one)
Take vertices as singleton sets and process the edges in this order with the implementation above, which keeps the lower-labeled root on a tie.
| Edge | Roots | Outcome | Components afterwards |
|---|---|---|---|
| accept: 1 goes beneath 0 | |||
| accept: 2 goes beneath 0 | |||
| reject: same set | |||
| accept: 4 goes beneath 3 | |||
| accept: 3 (size 2) goes beneath 0 (size 3) | |||
reject: find(4) follows and sets parent[4] to 0 |
Four edges are accepted, exactly , and the two rejected edges are the ones that would close a cycle. The rejected edge joins vertices that are not adjacent in the parent forest, yet the accepted edges already connect them. The final parent array is [0,0,0,0,0].
Counterexample mode
A partition alone cannot handle arbitrary edge deletion
A path graph with edges and a triangle with edges both give the partition . Delete edge from each. The path graph separates into and ; the triangle remains connected through 0.
The same stored partition and the same deletion therefore require different answers. The partition has forgotten which alternate paths existed. Ordinary union–find cannot resolve arbitrary deletions by simply reversing a parent assignment. A problem with deletions needs additional information or a different algorithm, rather than an unsupported split operation added to this interface.
Exercises
Quick check
(1. Separate a query's pointer changes from its answer)
Start from the eight-element parent table above, before any compression. Execute find(3) twice. Give each root-discovery hop count, the parent entries whose values change, the returned representatives and the number of components afterwards.
Solution · Solution 1
The first path is , so it takes two hops and changes only parent[3] from 2 to 0. The second path is , so it takes one hop and changes no entry. Both calls return 0, and there is still one component. Other branches, including the path from 7, have not been compressed by these calls.
Quick check
(2. A successful union need not flatten its new component)
Instead start from parent = [0,0,0,2,4,4,4,6], with two size-four components rooted at 0 and 4. Apply the implemented unite(3,7) with compression enabled. What is the final parent array? What path would the next find(7) traverse before its compression pass?
Solution · Solution 2
Finding 3 changes its parent to 0. Finding 7 follows and changes its parent to 4. The equal-size tie links root 4 beneath root 0. The final array is [0,0,0,0,0,4,4,4], and the next path from 7 is , taking two hops. Linking root 4 did not automatically change all its children's parents to 0.
Quick check
(3. Decide whether a representative must be the minimum label)
One component has members and root 0. Another has members and root 4. Under union by size, which root survives their union? Does the lower-label tie rule change this decision?
Solution · Solution 3
Root 4 survives because its component has size six, greater than two. The sizes do not tie, so the tie rule does not apply. The resulting set contains 0 but has representative 4. Equality of representatives still recognizes the correct component; minimum-label selection is not part of this structure's abstract contract.
Quick check
(4. Distinguish root linking from the whole union cost)
For a universe of nine elements using union by size, can a parent path have depth four under the doubling proof? Why is it incomplete to call the whole unite(x,y) operation constant-time just because it changes one root pointer?
Solution · Solution 4
Depth four would require at least elements, so it is impossible for under these rules; the bound is . Root linking is constant work once both roots are known, but discovering those roots requires two finds. The logarithmic bound accounts for their traversals and compression passes as well as the final link.