Skip to main content

The Union-Find Problem and the Naive Representation

What This Concept Is​

Disjoint-set union maintains a partition of a fixed universe. find(x) returns an implementation-selected representative; union(x,y) combines two classes. Equality of representatives expresses equivalence. Representatives need not be minimum elements or stable across unions. The lab initializes vertices 0..n-1, tracks component count/size, and returns whether a union actually changed the partition.

Why It Matters Here​

Representation choices move work between operations. This lesson corrects an important distinction: arbitrary list merging can be quadratic, but always moving the smaller list has a stronger aggregate bound.

Concrete Examples​

Direct labels. Each element stores a component label. Find is O(1). Relabeling every member of one arbitrarily chosen merged list can move 1,2,..., n-1 elements and total Θ(n²). However, if the smaller list is always relabeled, an element moves only when its new component is at least twice as large. It moves at most floor(log2 n) times, so all relabeling over n-1 successful unions totals O(n log n), plus operation overhead. These are different algorithms.

Parent forest. Roots point to themselves. Find follows parent pointers; linking already-known roots costs O(1), but union(x,y) also includes finding those roots. Arbitrary linking can make a chain, so total public union cost is not automatically constant.

For n=5, unions (0,1),(1,2),(3,4),(0,2) produce classes {0,1,2} and {3,4}. The last union changes nothing and must not double a size or decrease the component count. Two independent valid implementations may choose different roots.

Common Confusion / Misconceptions​

Root identity is not an application-level canonical label unless separately maintained. Sizes stored at nonroots need not remain meaningful after merging/compression; query size through the root. DSU describes undirected equivalence, not directed reachability, distances or a path witness.

How To Use It​

Compare each operation to explicit component sets or graph traversal. Test isolated vertices, repeated and self unions, empty universes and invalid IDs. Check every vertex belongs to exactly one acyclic parent tree and root sizes agree with an independent partition. Account for finds within union.

Check Yourself​

What changes the list bound from quadratic to n log n? Why is linking roots not the same operation as union on arbitrary elements? Why must repeated unions be idempotent?

Mini Drill or Application​

Start six singletons and union (0,1),(2,3),(1,3),(4,4). Feedback: three components, sizes 4,1,1. The self union returns false; root labels may vary.

Read This Only If Stuck​

Skiena: union-find, local chunk 078. Compare the actual heuristics shown there with the lab; do not attribute path compression to code that only links by size.