A partition that changes
When edges are added one at a time to an undirected graph, a component test asks whether two endpoints are already connected. The earlier Kruskal unit used a simple label scan for this test. A disjoint-set forest represents the same partition with parent pointers and supports merging without relabeling every vertex.
Definition 4.4.1
(Disjoint sets, find and union)
Fix elements. Initially each is in its own set. The operations are , which returns a representative of 's current set, and , which merges the two sets containing . Representatives need not be the smallest elements and may change after a merge. Two elements are in the same set exactly when their current representatives agree.
Parent forests and the rule
Definition 4.4.2
(Parent forest with size labels)
Store one parent pointer per element. A root points to itself; following parent pointers reaches its root. For each root store the number of elements in its tree. Initially every element is a root of size one. To find a representative, follow parents to a root. To merge, find both roots. If they agree, do nothing. Otherwise attach the smaller root under the larger root and update the larger root's size to the sum; break equal-size ties arbitrarily. A nonroot's stored size need not be consulted.
Proposition 4.4.3
(The forest represents the partition)
After any sequence of unions, the trees of the forest are exactly the current sets, and each root stores the number of elements of its tree.
Proof
(An invariant over operations)
Initially every tree is one set, and every root has size one. Linking one root below another joins exactly the two trees containing those roots, and it creates no cycle because the roots were distinct. No other tree changes. This matches the merge of the two sets. A union whose finds agree changes nothing, and the two elements were already in one set. Induction on the number of operations therefore maintains a forest whose trees are precisely the current sets. The surviving root's size is updated by addition, which is the size of the joined tree, so the size invariant is preserved as well.
Theorem 4.4.4
(Logarithmic parent depth without compression)
With union by size and no path compression, every parent path has at most edges. Thus each find, and each union including its two finds, takes time under constant-time array access.
Proof
(The tree of an element at least doubles whenever its depth grows)
Fix an element . Its depth increases only when the root of its current tree is attached below a different root, and then it increases by exactly one. Immediately before that link, its tree is no larger than the other tree; immediately afterward, the combined tree contains at least twice as many elements as 's previous tree. Between such increases its tree can only grow. Starting at size one and never exceeding , its depth can increase at most times. This proof holds for either choice on a size tie. A find follows one parent path, so its length is at most this depth bound plus the constant work of reading the root; a union does two finds and a constant amount of work.
Proof X-ray
What the doubling argument uses
The quantity that does the work is the size of the tree containing . It starts at one, never exceeds , and doubles at every step that costs a level; a quantity with those three properties can double only times. The doubling comes entirely from the size rule at the link: because the smaller tree is the one moved down, the tree containing is at most half of the merged tree. Equality is allowed, so the tie rule is irrelevant.
If the rule were reversed, so that the larger tree were attached below the smaller one, 's tree could be large while the merged tree is only one element bigger, and the doubling fails. Finds never change a pointer here, so no step other than a link alters a depth. The link moves the whole tree down by exactly one level, so the depth of is the number of links that carried its tree down, and the path length of a find from is this depth.
A worked sequence
Worked example 4.4.5
(Following a nonroot parent)
Start with singleton elements . Let a tie attach the second named root to the first. After and , roots each have size two. After , root has size four and follows . Next merge , then merge their size-two tree with 's size-four tree: root attaches below , regardless of which argument is listed first. The final size is six; both and have depth two.
Worked example 4.4.6
(The doubling bound is attained)
Take eight elements and attach the second named root to the first on ties. Perform , , , , giving four roots of size two. Then and give two roots of size four, and gives one root of size eight. The path from is , three edges, which equals . Every merge here joined two trees of equal size, so each one pushed the deepest element down by one level.
Worked example 4.4.7
(An edge that closes a cycle changes nothing)
Insert the undirected edges –, –, – and then – into the six-element example. The first three calls to build the tree rooted at of size four. For –, follows and follows ; both return , so the call does nothing and the sizes are unchanged. The edge closes a cycle in the graph, and the component structure is the same as before: the set together with and .
What the bound does and does not say
Proposition 4.4.8
(Cost of a sequence of operations)
Initializing the arrays costs . For subsequent operations, the total worst-case cost is in this model, and the arrays occupy space.
Proof
(Initialize once, then bound each operation)
Setting each element's parent to itself and its size to one takes time and uses two arrays of length . Each of the operations is one find or one union with two finds, and by the depth theorem each costs . Adding the costs gives the bound.
The logarithm follows from the explicit size rule. Path compression changes pointers during find and needs a separate analysis, so no inverse-Ackermann bound is claimed here.
Counterexample mode
Linking without the size rule can build a chain
Suppose each attaches the root of below the root of regardless of sizes. Take and call , , and so on up to . The first call sets the parent of to , the second sets the parent of to , and so on, so the path from is with seven edges, larger than . Under the size rule the same sequence stays shallow: each call joins a size-one tree to the large root, so no path has more than one edge. The depth theorem depends on the rule; arbitrary linking can create a long chain, and a find on element would cost seven pointer steps.
Common mistake
(Comparing immediate parents instead of roots)
In the first worked example the immediate parent of is , but its representative is . Comparing immediate parents can say that two elements are separate even though both parent paths end at the same root. A component test must use roots, not just one pointer step.
Common mistake
(Reading the size of a nonroot)
Only roots carry meaningful sizes. In the first worked example still stores the number two after , but its tree is now part of a set of size four whose root is . If a later union compared the stored number at with another root's size, it could attach the wrong way and break the doubling argument. Always compare the sizes stored at the two roots.
To maintain undirected connectivity under edge insertions, call union on each new edge's endpoints and compare finds for a query.
Proposition 4.4.9
(Connectivity under edge insertions)
If the edges of an undirected graph are inserted one by one and each insertion of calls , then the maintained partition equals the partition of the graph into connected components after every insertion.
Proof
(One insertion either merges two components or changes nothing)
Initially there are no edges and every vertex is its own component, matching the singleton sets. Inserting an edge adds no connection between vertices outside the components of and . If and were already in one component, the components are unchanged and union does nothing. Otherwise the two components become one, and union merges exactly the two corresponding sets. Induction over insertions proves the claim.
This structure does not by itself support edge deletions: deleting a bridge may split one maintained set into two. It also does not answer directed reachability, which is not an equivalence relation in general.
Exercises
Quick check
(If a tree of size three is merged with one of size seven, which root becomes the parent under this rule, and what is the new size?)
The smaller root goes below the larger.
Solution · Answer
The size-three root is attached below the size-seven root; the surviving root has size ten.
Quick check
(For , what maximum depth does the doubling bound give?)
Apply .
Solution · Answer
At most parent edges.
Quick check
(In the worked sequence, why does return even though 's immediate parent is ?)
Follow the pointers all the way up.
Solution · Answer
Find follows until the root ; the intermediate pointer is not itself the representative.
Quick check
(After inserting the sole undirected edge –, why can deleting it not be handled merely by leaving the union-find structure unchanged?)
Compare connectivity before and after the deletion.
Solution · Answer
With the edge present, are connected; after deletion they are separate. The unchanged structure still puts them in one set, so another method or rebuilding is required.