Motivation
Many graph algorithms repeatedly ask whether two vertices are already connected by the edges chosen so far. Recomputing connected components after every edge would discard useful information. A disjoint-set structure maintains a partition of the vertices and supports finding a representative of a set and merging two sets.
The implementation is a forest of parent pointers. Its efficiency depends on how trees are linked: always attaching one root to the other can make a long chain, whereas attaching the smaller tree below the larger tree limits the number of times any vertex's depth can increase. The doubling argument gives a concrete logarithmic bound without assuming a stronger inverse-Ackermann theorem.
Definitions
Definition 3.8.1
(Disjoint-set forest, find and union)
Initially there are singleton sets, one for each element. Each tree root is its own parent; every other node points to its parent. The elements in one tree form one set, and the root is that set's representative. Operation find(x) follows parent pointers from to its root. Operation union(x,y) first finds the two roots. If they differ, it links the root of the smaller tree below the root of the larger tree and updates the larger root's stored size. Ties may be resolved arbitrarily. A union of elements already in the same tree changes nothing.
Definition 3.8.2
(Depth and stored size)
A node's depth is the number of parent edges on its path to the root. The root's stored size is the number of elements in its tree. We first analyze union by size without path compression; later we discuss compression as an optional modification.
Theorems
Theorem 3.8.3
(Union-by-size height bound)
Starting from singleton trees and using union by size, every node has depth at most . Each find takes time and each union, including its two finds, takes time in the parent-pointer model.
Theorem 3.8.4
(Kruskal's component test)
In an undirected graph, processing edges in nondecreasing weight order and accepting an edge exactly when its endpoints have different disjoint-set representatives produces a minimum spanning forest. For a connected graph it produces a minimum spanning tree.
Proof: depth increases force doubling
Proof
(Union by size doubles the set at each depth increase)
Fix an element . Its depth increases only when the root of its current tree is attached below another root. At such a union, the other tree has at least as many nodes as 's tree. The new tree containing therefore has at least twice as many nodes as before. Subsequent unions never shrink a set.
Initially is in a tree of size one and has depth zero. After depth increases, its tree has size at least . No tree contains more than elements, so and . This reasoning applies to every element, even though different elements may experience their depth increases at different unions.
A find follows at most that many parent edges plus the final root check. A union performs two finds and a constant amount of size comparison, pointer change and size update. The stated time bounds follow. For there are no valid elements to find or unite; the depth statement is for nonempty structures.
Proof X-ray
Why the smaller tree matters
The proof follows one node and counts how often its depth can grow. The key move is to charge every increase to a doubling of the node's set. Depth rises by one only when the root of the node's own tree is linked below another root. The size rule makes the receiving tree at least as large, so the merged set has at least twice the old size. Three facts are used: the size rule, the fact that sets only merge and never shrink, and the start from singletons, which have size one and depth zero. The bound closes the argument because no set can exceed elements. If the size rule is dropped, a large tree can be linked below a singleton, which adds one to the depth of every node in the large tree while the set grows by a single element. The chain in the counterexample below is the result.
Proof: the disjoint-set invariant
Proof
(The forest tracks the components of the accepted edges)
Before any edge is processed, the chosen-edge graph has no edges and its connected components are singleton vertices. The disjoint-set forest represents exactly those components. Assume this is true before processing an edge .
If and have the same representative, the chosen edges already contain a path between them. Adding would create a cycle, so the algorithm rejects it and the component partition remains unchanged. If the representatives differ, adding joins two components and cannot form a cycle. The union operation merges exactly those two represented sets, so the invariant remains true.
Proof
(Cut exchange gives a minimum spanning forest)
Thus the accepted edges are precisely the cycle-free choices of Kruskal's algorithm. The standard cut-exchange argument proves their optimality: an accepted edge is a minimum-weight edge crossing the cut of one current component. Any previously scanned edge crossing the current component had endpoints in different components when scanned, because components only merge; it would therefore have been accepted. Every remaining crossing edge has weight at least the current edge by the sorted order. If an optimum spanning forest containing the earlier accepted edges does not contain it, adding it creates a cycle with another crossing edge of no smaller weight; exchanging those edges preserves a spanning forest and does not increase its weight. Induction retains an optimum containing all accepted edges.
When all edges have been considered, each connected component of the original graph is connected by accepted edges: otherwise an original edge on a path between two remaining components would have been accepted when scanned. The accepted forest is therefore spanning in every original component, and the exchange invariant makes it minimum-weight. Ties and negative weights do not invalidate the cut argument.
Worked examples
Worked example 3.8.5
(A size-doubling trace)
Start with singletons . Union and separately union ; each resulting tree has size two. Union their roots, breaking the tie by placing the second root under the first. A leaf in the second tree now has depth two, and its set has size four. The depth bound is .
Worked example 3.8.6
(A redundant union)
After and are in the same tree, union(a,b) finds the same root twice and makes no link. Updating the size again would be incorrect: the represented set has not gained any elements. The stored size must remain the number of distinct nodes in the tree.
Worked example 3.8.7
(A triangle in Kruskal's algorithm)
For triangle edges of weights , accept and merge , then accept and merge its components. When is scanned, its endpoints have the same representative, so reject it. The resulting spanning tree has total weight three.
Worked example 3.8.8
(A disconnected graph)
Suppose the graph has an edge of weight joining and an isolated vertex . Kruskal accepts the edge and leaves as a singleton tree. The answer is a minimum spanning forest with two components, not a spanning tree of the whole graph.
Path compression
Path compression modifies find(x) by redirecting visited nodes to the root after the root has been found. It preserves the represented partition: each redirected pointer stays within the same tree and leads to the same root. Stored root sizes remain valid because no element changes sets. Compression can only shorten a node's path at the moment it is applied.
Union by size together with path compression admits a stronger amortized bound, but that theorem requires a separate analysis and a precise sequence model. The elementary doubling argument above already supplies a logarithmic bound: after a depth increase caused by a size-based union, the containing set has doubled; compression can remove parent edges but does not create new ones that increase depth. We do not derive or claim the stronger bound here.
The representative is an implementation choice. Two correct runs with different tie-breaking can name different roots for the same set. Programs should compare representatives returned within the same structure, rather than depend on a particular vertex being the permanent name of a connected component.
Common mistakes
Counterexample mode
Arbitrary linking can create a chain
Starting from singleton roots , repeatedly attach the current root below the next singleton root. The result is a chain with at depth . The logarithmic proof fails because the tree containing is repeatedly attached to a smaller tree, so its size does not double at each depth increase.
Common mistake
(Merges are supported, deletions are not)
A disjoint-set structure supports merges, not general edge deletion. Removing an accepted graph edge could split a connected component, an operation not supported by these parent pointers alone. The Kruskal use is valid because it only adds accepted edges.
Common mistake
(Size and rank are different quantities)
Union by size and union by rank are related strategies but their stored quantities have different meanings. The size of a root is its current set cardinality. A rank used in another implementation should not be called a size unless it is maintained as one.
Cost of the graph algorithm
Let the graph have vertices and edges. Sorting edges takes comparisons. Initializing singleton sets takes time. Each of the edges causes two finds and at most one root link, so the elementary bound gives additional time when . The total is ; constants for are covered by the form.
The edge sort and the disjoint-set operations do different work. Faster merging does not remove the need to order arbitrary weights in this implementation. Conversely, if edges are already sorted, that input condition can eliminate the sort, but the connectivity operations and their correctness invariant remain necessary.
What the stored information certifies
Only a root's size needs to be current. When two roots are linked, the old size at the child root may be left in memory, but it must not later be treated as the size of an independent set. A find follows the parent chain to the current root before a union compares sizes. Implementations may clear the old value for clarity, but correctness depends on consulting sizes at current roots.
Common mistake
(Parent pointers are not input edges)
The forest is an auxiliary representation of a partition, not necessarily a subgraph of the input graph. A parent pointer records which representative was linked under another; it need not be one of the graph edges that caused the union. Therefore the parent chain is not automatically a path in the original graph. To output the minimum spanning forest, keep the accepted graph edges separately.
For example, if an accepted edge joins vertices and , the implementation links the roots of their two sets. Those roots may be neither nor . The union is still correct because the graph edge joins the two represented components, while the parent pointer merely records their merger. The proof of minimum total weight concerns the accepted graph edges, not the arbitrary orientation of parent pointers.
Summary
Union by size forces a set to at least double whenever one of its nodes moves down a level, giving logarithmic height. The disjoint-set partition tracks components of the accepted forest, while the cut-exchange argument proves Kruskal's optimality. Path compression preserves connectivity but its stronger amortized analysis is a separate result.
Exercises
Quick check
(With eight singleton elements, what is the largest depth permitted by the union-by-size theorem?)
Evaluate for .
Solution · Answer
The bound is . It is attained by repeatedly merging trees of equal size and following a leaf of the tree that is attached below the other root.
Quick check
(Why does a successful union update the size at the new root to the sum of the two old sizes?)
Which sets do the two roots represent?
Solution · Answer
The two roots represent disjoint sets. Linking them merges those sets without duplicating or deleting elements, so their cardinalities add. A union of elements with the same root does not merge distinct sets and must not add sizes.
Quick check
(In the triangle example, why is the third edge rejected even if its weight ties the second edge?)
Compare the representatives of its endpoints.
Solution · Answer
After accepting the first two edges, the endpoints of the third are already connected by a chosen path. The third edge would create a cycle. Equality of representatives detects this regardless of ties in weight.
Quick check
(What happens to a root's stored size after a path-compressing find?)
Does compression add or remove elements?
Solution · Answer
It remains unchanged. Compression changes parent pointers inside one set but does not add or remove elements. Only a successful union of distinct sets changes the stored cardinality of a root.
Exercise 3.8.9
(Prove by induction on the number of unions that, under union by size without compression, every tree of height has at least nodes.)
CoreProof
The height of a tree is the largest depth of its nodes. Ties in size may be broken arbitrarily.
Hint(1)
When two trees are linked, the new height is the larger of the height of the receiving tree and one more than the height of the attached tree.
Solution(3)
- 1
Check the starting trees
A singleton has height and nodes.
Because: Every tree begins as a singleton.
- 2
Link the smaller tree below the root of
Key step
Let have heights and satisfy the claim. The linked tree has height and .
Because: Union by size gives .
- 3
Treat the two cases for the height
∎If , then . If , then . In both cases , so the claim persists after every union.