Disjoint Set (Union-Find)

The Disjoint Set (Union-Find), also known as Disjoint Set Union (DSU), is an efficient data structure used to handle dynamic connectivity problems. It is primarily used to determine whether two elements belong to the same set and to merge two distinct sets into one. Due to its extremely low operation time complexity, the disjoint set is an indispensable tool in graph theory, network routing, image processing, and various algorithmic competitions.

The core idea lies in maintaining a "forest" structure, where each tree represents a connected component. By recording the parent node for each node, we can quickly determine if two nodes are in the same tree, thereby establishing whether they belong to the same set. When merging two sets, we point the root of one set to the root of the other, implementing the union operation.

Key Data Structure Design

To efficiently implement a disjoint set, we need to maintain two core arrays: parent and rank (or size).

  • parent array: parent[i] stores the index of the parent node for node i. If parent[i] == i, it indicates that i is the root of a set.
  • rank array: rank[i] records the approximate height (depth) of the tree rooted at i. This is primarily used for the "union by rank" strategy, which always attaches the shorter tree to the taller one. This maintains the flatness of the trees and reduces search depth.

Initially, each node is considered an independent set, so parent[i] = i, and the rank of all nodes is initialized to 0.

Two Core Operations: Find and Union

The operations of a disjoint set mainly consist of "Find" and "Union", typically used in conjunction with two optimization strategies: path compression and union by rank.

1. Find Operation

The purpose of the find operation is to locate the root node of the set to which a given node belongs. To accelerate subsequent operations, we employ the path compression technique. During the recursive or iterative search process, not only does it return the root node, but it also directly points the parent of all nodes along the path to the root. This makes the time complexity for finding any node in that subtree approach constant time in the future.

def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])  # Path compression
    return parent[x]

2. Union Operation

The purpose of the union operation is to merge two distinct sets into one. To maintain tree balance, we adopt the union by rank strategy: compare the rank values of the two roots and make the tree with the smaller rank the child, attaching it under the tree with the larger rank. If the heights of the two trees are equal, increment the rank of one of them.

def union(parent, rank, x, y):
    rootX = find(parent, x)
    rootY = find(parent, y)
    
    if rootX != rootY:
        if rank[rootX] < rank[rootY]:
            parent[rootX] = rootY
        elif rank[rootX] > rank[rootY]:
            parent[rootY] = rootX
        else:
            parent[rootY] = rootX
            rank[rootX] += 1

Algorithm Complexity Analysis

The power of the disjoint set lies in its astonishing time efficiency. After optimization with path compression and union by rank, for $N$ elements and $M$ operations (finds or unions), the total time complexity is $O(M \log^* N)$, where $\log^* N$ is the iterated logarithm function. This means that even if $N$ reaches $10^{18}$, the value of $\log^* N$ will not exceed 5. In practical applications, its performance is often much faster than $O(1)$.

This efficiency allows the disjoint set to easily handle connectivity judgment problems involving large-scale data, making it one of the ultimate solutions for "dynamic connectivity problems".

Typical Application Scenarios

Identifying Friend Circles in Social Networks

Assume there is a social platform where users can establish friend relationships. We need to quickly answer two questions:

  1. Are user A and user B in the same friend circle?
  2. If C and D become friends, has the friend circle containing A expanded?

We can treat each user as a node and friend relationships as edges. Initially, each user forms its own set. When two users add each other as friends, perform the union operation; when checking the relationship between two users, perform the find operation and compare if their roots are the same.

Image Segmentation

In image processing, if two adjacent pixels have similar colors, they are considered to belong to the same region (connected component). We can traverse the image and merge adjacent pixels with similar colors. Finally, each connected component corresponds to an independent set, and by counting the number of sets, we can determine how many distinct color blocks exist in the image.

Summary and Best Practices

The disjoint set is a concise yet powerful data structure. Its core value lies in achieving extremely high query efficiency at the cost of minimal space overhead. When writing code, remember the following two points:

  1. Path compression is essential; it reduces the find complexity from $O(\log N)$ to nearly constant time.
  2. Union by rank is equally important; it prevents the tree from degenerating into a linked list, ensuring the tree depth remains within an extremely small range.

Mastering the disjoint set will enable you to handle most algorithmic challenges involving set merging and querying, whether it's the connected components problem on LeetCode or dependency management in real-world engineering projects. It can provide elegant solutions.