Union-Find with Optimizations

1. What is a Disjoint Set Union (DSU)?

A DSU is a data structure that manages a collection of disjoint sets. Think of the vertices in a graph at the beginning of Kruskal's algorithm: each vertex is its own separate component, or its own set. The DSU specializes in two main operations:

1. find(element): Determines which set an element belongs to. It returns a single, consistent "representative" or "leader" for that set.
2. union(element1, element2): Merges the two sets containing these elements into a single set.

These operations directly map to what Kruskal's needs: before adding an edge (u, v), we check if find(u) == find(v). If they are the same, the vertices are already in the same component, and adding the edge would create a cycle. If not, we perform a union(u, v) to merge their components.

To build a strong intuition for this, let's start with a video that explains the core idea and its direct application to detecting cycles in a graph.

2. Implementing the DSU: Trees and Parent Pointers

A common and effective way to represent these sets is as a collection of trees. Each tree represents one set, and the root of the tree serves as the set's representative.

Initially, every element is in its own set, so we start with a "forest" where each element is a single-node tree. To implement this, we use a parent array. If parent[i] == i, then i is the root of its tree (and the representative of its set).

• make_set(v): To create a new set with a single element v, we simply set parent[v] = v.
• find_set(v): To find the representative of v, we traverse up the tree from v by following the parent pointers until we reach a node that is its own parent (the root).
• union_sets(a, b): To merge the sets containing a and b, we first find their representatives. If they are different, we make one root the child of the other by updating its parent pointer.

This approach seems simple, but it has a major flaw. If we aren't careful about how we perform the union operation, we can end up with very tall, skinny trees that look like linked lists. In this worst-case scenario, a find operation would have to traverse the entire chain, taking $O(n)$ time, which is far too slow.

The following resource provides a clear explanation and code for this naive approach.

3. The Optimizations: Making DSU Fast

To overcome the $O(n)$ worst-case, we introduce two powerful optimizations that, when combined, bring the average time per operation down to nearly constant.

Optimization 1: Union by Rank (or Size)

This optimization addresses the problem of creating tall, unbalanced trees during the union operation. The strategy is simple: when merging two trees, always attach the root of the shorter tree to the root of the taller tree. This heuristic prevents the tree heights from growing unnecessarily.

We keep track of the "rank" of each tree, which is an upper bound on its height.

• Initially, all elements are in sets of rank 0.
• When unioning two trees of different ranks, the root of the smaller-rank tree becomes a child of the root of the larger-rank tree. The rank of the larger tree does not change.
• When unioning two trees of the same rank, we can pick either root as the new parent. The key is that the new root's rank must be incremented by one.

A similar heuristic is Union by Size, where we attach the tree with fewer nodes to the root of the tree with more nodes. Both achieve the same goal of keeping the trees shallow.

Optimization 2: Path Compression

This optimization speeds up the find operation. The idea is that after we traverse a path from a node v up to its root r, we can make the path shorter for future find calls. We do this by re-attaching every node on that path directly to the root.

The next time we call find on v or any of its ancestors, the lookup will be much faster.

With these two optimizations combined, the DSU data structure becomes incredibly efficient.

4. Implementation and Analysis

Let's see how to combine these ideas into a working implementation. The following video provides a detailed walk-through, explaining the logic for both optimizations and then putting it all together in C++ code.

The core logic for an optimized DSU can be summarized in this pseudocode:

class DisjointSetUnion {
    parent = [];
    rank = []; // or size = [] for union by size

    constructor(n) {
        // Initialize n sets, each with one element
        for (let i = 0; i < n; i++) {
            this.parent[i] = i;
            this.rank[i] = 0; // or this.size[i] = 1
        }
    }

    // Find with Path Compression
    find(i) {
        if (this.parent[i] === i) {
            return i;
        }
        // Recursively find the root and set it as the parent of i
        this.parent[i] = this.find(this.parent[i]);
        return this.parent[i];
    }

    // Union by Rank
    union(i, j) {
        const root_i = this.find(i);
        const root_j = this.find(j);

        if (root_i !== root_j) {
            if (this.rank[root_i] > this.rank[root_j]) {
                this.parent[root_j] = root_i;
            } else if (this.rank[root_i] < this.rank[root_j]) {
                this.parent[root_i] = root_j;
            } else {
                // Ranks are equal, attach one to the other and increment rank
                this.parent[root_j] = root_i;
                this.rank[root_i]++;
            }
        }
    }
}

For complete, working examples in various languages, including Python and JavaScript which may be more familiar to you from your web development background, the following resource is excellent.

Complexity Analysis

When both Union by Rank/Size and Path Compression are used, the amortized time complexity of the find and union operations is remarkably low: $O(\alpha (n))$, where $\alpha (n)$ is the Inverse Ackermann Function.

This function grows so slowly that for any practical input size n (e.g., $n<10^{600}$), $\alpha (n)$ is less than 5. For all intents and purposes in software engineering, you can consider this nearly constant time. The space complexity is $O(n)$ to store the parent and rank/size arrays.

Conclusion

You have now mastered the implementation of the Disjoint Set Union data structure. This is a significant step, as you've moved from using an abstract tool to understanding its inner workings and the optimizations that make it so efficient.

Key Takeaways:

• A DSU is specialized for tracking membership in a collection of disjoint sets, with core operations find and union.
• It is naturally represented as a forest of trees, where each tree root is the set's representative.
• A naive implementation can lead to $O(n)$ performance, which is too slow.
• Union by Rank/Size keeps the trees shallow by attaching shorter/smaller trees to taller/larger ones.
• Path Compression flattens the trees during find operations by making all nodes on a path point directly to the root.
• Together, these optimizations yield a nearly constant amortized time complexity of $O(\alpha (n))$ per operation.

Preview of the Next Lesson:
We have now covered four major graph algorithms: Dijkstra's, Bellman-Ford, Kruskal's, and Prim's. In our next lesson, we will move from implementation to analysis. We will compare and contrast these algorithms, discussing their trade-offs, constraints, and ideal use cases. Your deep understanding of the Union-Find data structure will be crucial for properly evaluating the performance profile of Kruskal's algorithm.