Implementing Disjoint Set Union (DSU)

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

A Disjoint Set Union (DSU) data structure, also known as Union-Find, manages a collection of disjoint sets. "Disjoint" simply means that no element belongs to more than one set. Think of it like a group of people. Initially, everyone is in their own individual group (a set of size one). As we discover relationships (e.g., friendships), we merge these groups.

DSU is built to do two things very, very fast:

1. find(element): Determine which set an element belongs to. It does this by returning a single, unique "representative" or "leader" for that set.
2. union(element1, element2): Merge the two sets containing element1 and element2 into a single set.

How does this help us? To check if two nodes are connected, we simply find the representative for each. If their representatives are the same, they are in the same set, meaning they are connected.

To get a clear overview of these concepts, let's start with a video.

2. Representing Disjoint Sets and the Need for Optimization

The most common way to represent these sets is using trees, where each set is a tree and the root of the tree is the set's representative. We can implement this entire structure using a simple array, let's call it parent.

For a set of n elements (numbered 0 to n-1):

• parent[i] stores the parent of element i.
• If parent[i] == i, then i is the root of its tree (the representative of its set).

The find(i) operation works by traversing up from i using the parent array until it reaches the root. The union(i, j) operation first finds the roots of i and j, and then makes one root the parent of the other.

However, a naive union operation (e.g., always making j's root the parent of i's root) can lead to very tall, skinny trees, essentially becoming linked lists. In this worst case, a find operation could take $O(N)$ time. To make DSU truly powerful, we need optimizations.

The following resources explain these optimizations beautifully.

3. Key Optimizations: Union by Rank/Size and Path Compression

As you saw in the video, two optimizations dramatically improve DSU's performance:

1. Union by Rank or Size (Weighted Union):
This optimization minimizes the height of the trees. When uniting two sets, instead of arbitrarily connecting them, we attach the smaller tree to the root of the larger tree.

• Union by Rank: We track the "rank" (an upper bound on the height) of each tree. The tree with the lower rank is attached to the root of the tree with the higher rank. If ranks are equal, one is attached to the other, and the rank of the new root is incremented.
• Union by Size: We track the number of elements (size) in each tree. The tree with fewer elements is attached to the root of the one with more elements. This is often simpler to implement and just as effective.

2. Path Compression:
This optimization flattens the tree structure whenever we perform a find operation. When we find the root of an element x, we make every node on the path from x to the root point directly to the root. This makes subsequent find operations on any of those nodes extremely fast.

When used together, these optimizations make the DSU operations run in nearly constant time on average. The amortized time complexity is $O(\alpha (N))$, where $\alpha (N)$ is the Inverse Ackermann function. This function grows so slowly that for any practical input size you'll encounter in an interview or competition, it's less than 5. So, for all practical purposes, the complexity is considered constant time.

4. Java Implementation

Now, let's translate these concepts into a Java class. You'll build a UnionFind class that incorporates both Path Compression and Union by Size/Rank.

Let's consolidate the implementation for Union by Size with Path Compression, as it's a very common and effective combination.

public class UnionFind {
    private int[] parent; // parent[i] = parent of element i
    private int[] size;   // size[i] = number of elements in subtree rooted at i
    private int count;    // Number of disjoint sets

    public UnionFind(int n) {
        parent = new int[n];
        size = new int[n];
        count = n; // Initially, n elements in n disjoint sets
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    /**
     * Finds the representative of the set containing element i, with path compression.
     */
    public int find(int i) {
        if (parent[i] == i) {
            return i;
        }
        // Path compression: set parent[i] to the root
        return parent[i] = find(parent[i]); 
    }

    /**
     * Merges the sets containing elements i and j, using union by size.
     */
    public void union(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);

        if (rootI == rootJ) {
            return; // Already in the same set
        }

        // Union by size: attach smaller tree to the root of larger tree
        if (size[rootI] < size[rootJ]) {
            parent[rootI] = rootJ;
            size[rootJ] += size[rootI];
        } else {
            parent[rootJ] = rootI;
            size[rootI] += size[rootJ];
        }
        count--; // One set has been merged, so decrement the count
    }

    /**
     * Returns true if elements i and j are in the same set.
     */
    public boolean connected(int i, int j) {
        return find(i) == find(j);
    }
    
    /**
     * Returns the number of disjoint sets.
     */
    public int getCount() {
        return count;
    }
}

Conclusion

You have now learned one of the most elegant and efficient data structures in computer science. The Disjoint Set Union is your go-to tool for any problem involving partitioning elements into sets and dynamically checking for connectivity.

Key Takeaways:

• DSU efficiently handles dynamic connectivity problems with its find and union operations.
• It's represented as a forest of trees, implemented with a simple parent array.
• Naive implementations are slow, leading to $O(N)$ performance in the worst case.
• The combination of Path Compression and Union by Rank/Size optimizes operations to have a nearly constant amortized time complexity, $O(\alpha (N))$.
• The implementation is concise and powerful, making it a valuable tool for interviews and competitive programming.

Preview of the Next Lesson:
Now that you have this powerful tool, what can you do with it? In the next lesson, we will see a direct and classic application of DSU. We will use it to implement Kruskal's algorithm to find the Minimum Spanning Tree (MST) of a graph. You'll see how DSU's ability to efficiently detect cycles is central to how Kruskal's algorithm works.