Disjoint Set Union (DSU)

Definition

Disjoint Set Union (also called Union-Find) is a data structure that tracks elements which are split into one or more disjoint (non-overlapping) sets. Its main job is to quickly tell you if two items belong to the same group or to merge two groups together.

How it Works

DSU relies on two main operations:

1. Find: “Who is the leader of this group?” If item A and item B have the same leader, they are in the same group.
2. Union: “Merge these two groups.” We make the leader of one group point to the leader of the other group.

Real-World Analogy:

Imagine social circles. Initially, everyone is their own circle.

• If Alice becomes friends with Bob, you Union their circles.
• If Bob is friends with Charlie, you Union their circles.
• Now, to check if Alice knows Charlie (indirectly), you use Find to see if they belong to the same “friendship network” (Set).

Example

Initial: {1}, {2}, {3}

Union(1, 2): Sets become {1, 2}, {3}. Leader of 1 is 2.

Union(2, 3): Sets become {1, 2, 3}. Leader of 2 is 3.

Find(1): Follows path $1 \rightarrow 2 \rightarrow 3$. Leader is 3.

Code Example (Python)

Python

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, i):
        if self.parent[i] == i:
            return i
        # Path Compression: Point directly to the ultimate leader
        self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

    def union(self, i, j):
        root_i = self.find(i)
        root_j = self.find(j)
        if root_i != root_j:
            self.parent[root_i] = root_j # Merge groups

dsu = DSU(5)
dsu.union(0, 1)
dsu.union(1, 2)
print(dsu.find(0) == dsu.find(2)) # Output: True (0 and 2 are connected)

Complexity Analysis

• Time Complexity: Nearly O(1) (amortized) using Path Compression and Union by Rank. It’s incredibly fast.
• Space Complexity: O(n)

Use Cases

• Kruskal’s Algorithm: Finding the Minimum Spanning Tree in a graph.
• Cycle Detection: Checking if adding a connection in a network creates a loop.
• Image Processing: Finding connected regions of pixels.