Disjoint Set Union, also called Union-Find, is a data structure for tracking groups of connected items. It is useful when a program needs to quickly answer whether two elements belong to the same set. This cheat sheet helps students remember the core operations, array meanings, and optimization rules.
It is especially important for graph problems such as connected components and Kruskal's minimum spanning tree algorithm.
The structure stores each element's parent in an array such as parent[x], where roots represent whole sets. The main operation find(x) returns the representative root of x's set, and union(a,b) merges two sets if their roots differ. Path compression makes future find operations faster by pointing nodes directly to the root.
Union by size or rank keeps trees shallow, giving nearly constant amortized time per operation.
Key Facts
- In make-set initialization, set parent[x] = x for every element x so each element starts as its own set.
- The representative of a set is its root, which satisfies parent[root] = root.
- The operation find(x) returns the root of x by following parent pointers until parent[x] = x.
- Path compression updates nodes during find so that parent[x] = find(parent[x]), making later searches faster.
- The operation union(a,b) computes ra = find(a) and rb = find(b), then links one root under the other if ra != rb.
- Union by size attaches the smaller tree under the larger tree and updates size[newRoot] = size[rootA] + size[rootB].
- Union by rank attaches the lower-rank root under the higher-rank root, and if ranks are equal, one rank increases by 1.
- With path compression and union by size or rank, m DSU operations on n elements run in O(m alpha(n)) amortized time, where alpha(n) grows extremely slowly.
Vocabulary
- Disjoint Set Union
- A data structure that maintains a collection of non-overlapping sets and supports finding and merging those sets.
- Find
- The operation find(x) returns the representative root of the set containing element x.
- Union
- The operation union(a,b) merges the sets containing a and b if they are currently different sets.
- Representative
- The representative is the root element used as the name or identifier for an entire set.
- Path Compression
- Path compression is an optimization that makes each visited node point directly to the root during find.
- Union by Rank
- Union by rank is an optimization that attaches the shallower tree under the deeper tree to keep parent trees short.
Common Mistakes to Avoid
- Forgetting to initialize parent[x] = x is wrong because find cannot identify roots correctly when elements do not start as their own sets.
- Setting parent[a] = b directly in union(a,b) is wrong because a and b may not be roots, so it can create an incorrect tree structure.
- Comparing parent[a] and parent[b] instead of find(a) and find(b) is wrong because two elements can have different immediate parents but still share the same root.
- Updating size or rank on a non-root is wrong because size and rank should describe the root's tree, not an arbitrary element inside the set.
- Using recursive find without path compression in large problems is risky because the trees can become tall and cause slow performance or stack depth issues.
Practice Questions
- 1 Start with elements 1 through 5 in separate sets. After union(1,2), union(3,4), and union(2,3), how many sets remain?
- 2 Given parent[1] = 1, parent[2] = 1, parent[3] = 2, and parent[4] = 4, what root does find(3) return before path compression?
- 3 Using union by size, suppose root A has size 6 and root B has size 2. After union(A,B), which root should become the parent and what is the new size?
- 4 Why does DSU work well for checking whether adding an edge to an undirected graph would create a cycle?
Understanding Disjoint Set Union (Union-Find) Reference
A useful way to picture this structure is as a forest of rooted trees. Each tree stands for one group. The root acts as a label for every item below it, even though the root itself is just one ordinary item chosen by the algorithm.
The important rule is that membership is determined by the final root, not by an item's immediate parent. Two items can have different parents yet belong to the same group. This rule is an invariant, meaning it must remain true after every operation.
When tracing a program by hand, draw arrows from each item to its parent. Stop only at a self-pointing root. This makes it much easier to catch mistakes in a union operation.
The optimizations work because tall trees waste time. Imagine a chain where one item points to the next for many steps before reaching the root. A find operation must walk through every link in that chain.
Path compression repairs the route while it searches. Nodes visited on the route are redirected toward the root, so later searches skip most intermediate nodes. Union by size or rank prevents long chains from forming in the first place.
Size records how many items are in a tree. Rank is a rough measure of tree height, not necessarily the exact height after compression. Students should not mix the two update rules.
If using size, update the size of the new root. If using rank, increase a rank only when two equal-rank roots are joined.
Disjoint Set Union is especially useful when connections arrive one at a time. In a social network model, a new friendship can merge two friend groups. In a network of computers, a cable can connect two previously separate components.
In a maze or grid, open passages can join regions. Before adding an edge in a graph, compare the roots of its endpoints. If the roots differ, the edge joins separate components.
If the roots match, there is already a path between those endpoints. This is why the structure can detect whether adding an undirected edge creates a cycle. In Kruskal's algorithm, edges are considered from lowest weight upward.
An edge is accepted only when its endpoints have different roots. This avoids cycles while building a minimum spanning tree.
Implementation details matter more than they first appear. A union function should always call find on both inputs before deciding what to link. Linking the original inputs instead of their roots can break the tree structure or make size information wrong.
A failed union, where both inputs already have the same root, should not change sizes or ranks. Decide whether elements are numbered from zero or from one before creating arrays. Allocate enough space for that choice.
Recursive find is short and clear, but an iterative version can avoid call stack limits when code is used without balancing rules. The best way to test a DSU is to use small examples. Merge a few pairs, check expected representatives, try a repeated merge, then verify that compression does not change which items are connected.