Disjoint Set Union (Union-Find) Data Structure

What is Disjoint Set Union (DSU)?

DSU, also known as Union-Find, is a data structure that keeps track of a partition of a set into disjoint subsets. It supports two useful operations efficiently:

• Find: Determine which subset a particular element belongs to. This can be used to check if two elements are in the same subset.
• Union: Join two subsets into a single subset.

Key Concepts and Optimizations

• Path Compression: During the find operation, make each node point directly to the root, flattening the structure and speeding up subsequent queries.
• Union by Size/Rank: Attach the smaller tree under the root of the larger tree to keep the tree shallow, ensuring near-constant time operations.

Python Implementation

class DisjointSetUnion:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n

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

    def union(self, a, b):
        rootA = self.find(a)
        rootB = self.find(b)

        if rootA != rootB:
            # Union by size
            if self.size[rootA] < self.size[rootB]:
                rootA, rootB = rootB, rootA
            self.parent[rootB] = rootA
            self.size[rootA] += self.size[rootB]

# Usage Example
dsu = DisjointSetUnion(5)  # create 5 elements (0 to 4)
dsu.union(0, 1)
dsu.union(1, 2)
dsu.union(3, 4)
print("Parent array:", dsu.parent)
print("Are 0 and 2 connected?", dsu.find(0) == dsu.find(2))  # True
print("Are 0 and 4 connected?", dsu.find(0) == dsu.find(4))  # False

Applications

• Kruskal’s Minimum Spanning Tree algorithm
• Detecting cycles in undirected graphs
• Network connectivity and dynamic connectivity problems
• Image processing for grouping pixels