Union-Find with Path Compression and Union by Rank

1. The Core Problem and a Naive Approach

Imagine you have a set of elements, and you want to group them into components. You need to be able to perform two main operations:

1. Find: Check which component (or set) an element belongs to.
2. Union: Merge two components into a single one.

A common application is tracking connected components in a graph. Initially, each vertex is its own component. As you add an edge between two vertices, you union their components. At any point, you can use find to check if two vertices are already connected.

Let's start by watching a video that introduces this concept and its applications in dynamic graphs.

A simple way to implement this is to represent our sets as a forest of trees, where each tree corresponds to a set. We can use a simple array, let's call it parent, where parent[i] stores the parent of element i. The root of a tree is the representative of its set, and it's identified by the condition parent[i] == i.

• make_set(i): parent[i] = i. Each element starts as its own set.
• find_set(i): Starting from i, traverse up the tree by following parent pointers until you reach the root.
• union_sets(a, b): Find the root of a and the root of b. If they are different, make one root the parent of the other.

This naive approach has a significant flaw. A sequence of unions could create a degenerate tree that looks like a long chain. In this worst-case scenario, a find_set operation would take $O(n)$ time, as it would have to traverse the entire chain. To achieve the high efficiency that makes DSU so powerful, we need a couple of clever optimizations.

2. Optimization 1: Union by Rank

The first optimization addresses how we perform the union operation. To prevent trees from becoming unnecessarily tall, we should be strategic about which tree we attach to the other. The union by rank heuristic does just that.

The "rank" of a root node is an upper bound on the height of its tree. When we union two sets, the rule is: always attach the root of the tree with the lower rank to the root of the tree with the higher rank.

• If ranks are different, the rank of the new root doesn't change.
• If ranks are the same, we can attach either way, and we increment the rank of the new root by one.

This simple rule helps keep the trees balanced and shallow.

To see a step-by-step walkthrough and understand the intuition, let's return to the "take U forward" video.

An alternative, equally effective heuristic is Union by Size, where you track the number of elements in each set and always attach the smaller set to the larger one. The principle is the same: minimize the "effort" required to update parent pointers and keep the resulting tree as balanced as possible.

3. Optimization 2: Path Compression

The second optimization, path compression, dramatically speeds up the find_set operation. The idea is that whenever we traverse a path from a node up to the root to find the set's representative, we can flatten that path along the way.

Specifically, after a call to find_set(i) returns the root r, we make every node on the path from i to r point directly to r.

This optimization doesn't change the correctness of find_set—it still returns the same root—but it makes the tree much flatter, benefiting subsequent calls. Path compression is often implemented elegantly using recursion.

Let's see a final video segment that explains this technique.

4. Implementation and Complexity

With both optimizations—union by rank/size and path compression—the DSU data structure becomes incredibly fast. Let's look at the C++ implementation, which is quite concise.

The time complexity analysis of DSU is famous in computer science. When both optimizations are used, the amortized time per operation is $O(\alpha (n))$, where $\alpha (n)$ is the inverse Ackermann function.

This function grows so slowly that for any practical value of $n$ you would encounter (e.g., $n<10^{600}$), $\alpha (n)$ is less than 5. Therefore, for all practical purposes, the DSU operations can be considered to run in nearly constant time. This remarkable efficiency is why DSU is the go-to data structure for problems involving disjoint sets.

Conclusion

In this lesson, we've unpacked the Union-Find data structure, an essential tool for managing disjoint sets. You learned not just how it works, but why it's so efficient.

Key Takeaways:

• A Disjoint Set Union (DSU) or Union-Find data structure tracks a collection of disjoint sets and supports efficient union and find operations.
• It is commonly implemented as a forest of trees, where each tree represents a set and its root is the set's representative.
• A naive implementation can lead to $O(n)$ complexity for operations due to tall, chain-like trees.
• The union by rank (or size) heuristic combats this by always attaching the smaller tree to the root of the larger tree during a union, keeping the trees shallow.
• Path compression further optimizes the structure by flattening the tree during find operations, making all nodes on a lookup path point directly to the root.
• Together, these optimizations give DSU a nearly constant amortized time complexity, $O(\alpha (n))$.

Preview of the Next Lesson:
Now that we have mastered the Union-Find data structure, we are ready to apply it. In the next lesson, we will learn Kruskal's algorithm, a classic greedy algorithm for finding a Minimum Spanning Tree. You will see firsthand how Union-Find's ability to efficiently detect cycles is the cornerstone of this algorithm.