Disjoint Set Union

The Disjoint Set Union (DSU) - also known as a Union-Find data structure - allows us to efficiently merge any two distinct sets into a single set, and quickly determine whether any two elements belong to the same set.

In a practical scenario like computer networking, DSU can easily track whether any two machines are connected, dynamic updates like connecting two separate subnets with a physical cable.

This data structure plays a vital role in network connectivity and forms the backbone of several graph algorithms, most notably Kruskal’s algorithm for finding the Minimum Spanning Tree (MST).

The Core Concept

Imagine we currently have 3 separate sets: [1, 3, 5], [2, 4], and [7].

By convention, each set designates a specific element as its root or representative (indicated in bold). To check if two elements belong to the same set, we simply compare their roots. For example, the root of element 3 is 1, and the root of element 5 is also 1; therefore, 3 and 5 are in the same set. When merging set A and set B, we simply point the root of the elements in B to the root of set A, and we’re done.

While the array-based analogy works on paper, DSU is typically implemented under the hood as a tree-like graph structure. Each tree represents a disjoint set. Implementing DSU using trees makes the code incredibly concise and remarkably efficient.

Note: To see this in action, check out visualgo.net for an excellent interactive visualization of how DSU operates.

Find Root

To locate the root of a given node (which corresponds to an element), we need to track its parent pointer.

We define the base case as $par(root) = root$. In other words, a root node is its own parent.

Thus, starting from any node $x$, we just traverse upwards to $par(x)$ until we hit the root node :3

How fast we transition from node $x$ to its root depends heavily on the depth of the tree. In the worst-case scenario (a degenerate tree where nodes form a straight line), searching for the root of deeply nested nodes repeatedly becomes highly inefficient.

To optimize performance, once we find the root, we directly reassign $par(x) \leftarrow root$ for every node $x$ visited along the lookup path. This way, subsequent root lookups for these nodes take just a single hop. This brilliant optimization technique is known as path compression.

Union

To merge two trees-specifically, tree A (containing node $x$) and tree B (containing node $y$):

We simply compute $u \leftarrow findRoot(x)$ and $v \leftarrow findRoot(y)$, then assign $par(u) \leftarrow v$ (or vice versa-both are technically correct before optimization).

If $findRoot(x) == findRoot(y)$, it means both elements already belong to the same set.

To further boost efficiency during a union operation, we can utilize a clever trick called union by size. We always attach the smaller tree under the root of the larger tree, making the larger root the parent of the whole merged structure.

Implementation

DSU with Path Compression

// Initially, we start with n disjoint trees, where each node is its own parent.
void initialize(int n) {
    for (int i = 1; i <= n; ++i)
        par[i] = i;
}

int findRoot(int u) {
    if (par[u] == u) return u; // Found the root
    return par[u] = findRoot(par[u]); // Path compression trick
}

void unionSets(int x, int y) {
    par[findRoot(x)] = findRoot(y);
}

Super clean, and the average time complexity is already a blazing fast $O(\log n)$.

DSU with Union by Size

Combining path compression with union by size transforms our DSU into an absolute speed demon.

For this optimization, we need to track an extra piece of information: $size(u)$, which tells us the total number of nodes in the tree rooted at $u$.

When merging two trees rooted at $u$ and $v$, if $size(u) > size(v)$, we set $par(v) = u$. Otherwise, we set $par(u) = v$. We also need to update the size accordingly. For instance, if $size(u) > size(v)$, tree $v$ adopts tree $u$ as its parent, so $size(u) \leftarrow size(u) + size(v)$.

Pro tip: You can actually reuse the existing par[] array instead of allocating a separate size[] array with a slight tweak.

Instead of setting $par(root) = root$, we can define $par(root) = -size(root)$. Since the value is negative, we instantly know it’s a root node, and evaluating $-par(root)$ instantly yields the $size(root)$.

// Initially, there are n trees, each with a size of 1.
void initialize(int n) {
    for (int i = 1; i <= n; ++i)
        par[i] = -1;
}

int findRoot(int u) {
    if (par[u] < 0) return u; // Found the root
    return par[u] = findRoot(par[u]); // Path compression trick
}

void unionSets(int x, int y) {
    x = findRoot(x); 
    y = findRoot(y);
    if (x == y) return; // Already in the same set
    
    if (par[x] > par[y]) 
        std::swap(x, y);
        
    par[x] += par[y]; // Union by size
    par[y] = x;
}

Nice! Absolutely blazing fast.

Time Complexity

When implementing DSU using only path compression, the average time complexity scales to $O(\log n)$ per operation (according to CP-Algorithms).

However, when you implement DSU with both path compression and union by size, the amortized time complexity drops down to an astonishing $O(\alpha(n))$, where $\alpha(n)$ represents the inverse Ackermann function. While the math behind it is quite intense, all you need to know is that it grows incredibly slowly. In fact, $\alpha(n) \le 4$ for all practical values of $n$ (even up to a number with 600 digits!).

Practice Problems

DSU is widely leveraged in Minimum Spanning Tree tasks, graph connectivity problems, and set-merging challenges. Give these a shot:

1. Minimum Spanning Tree - SPOJ
2. Water Jugs / Thùng nước - VNOJ

References

1. Disjoint Set Union - CP-Algorithms
2. disjointset.cpp - kc97ble