Union Find in 5 minutes — Data Structures & Algorithms

Introduction

In this tutorial, we will explore the Union-Find data structure, also known as Disjoint Set Union (DSU). This structure is essential in various applications, such as network connectivity, image processing, and clustering. We will break down the concepts and provide practical code examples to help you understand how to implement Union-Find efficiently.

Step 1: Understand the Basics of Union-Find

• Union-Find is a data structure that keeps track of a partition of a set into disjoint (non-overlapping) subsets.
• Key operations:
  • Find: Determine which subset a particular element is in. This can be used to check if two elements are in the same subset.
  • Union: Combine two subsets into a single subset.

Practical Tip

• Think of Union-Find as a way to manage a group of related components where you want to quickly check connectivity.

Step 2: Implement the Find Operation

• The Find operation can be optimized using path compression to flatten the structure of the tree whenever Find is called.

Code Example

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))

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

Explanation

• In the find method, we recursively find the root of the element, compressing the path along the way for efficiency.

Step 3: Implement the Union Operation

• The Union operation can be optimized using union by rank, which ensures that the smaller tree is always attached under the root of the larger tree.

Code Example

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

    def union(self, p, q):
        rootP = self.find(p)
        rootQ = self.find(q)

        if rootP != rootQ:
            if self.rank[rootP] > self.rank[rootQ]:
                self.parent[rootQ] = rootP
            elif self.rank[rootP] < self.rank[rootQ]:
                self.parent[rootP] = rootQ
            else:
                self.parent[rootQ] = rootP
                self.rank[rootP] += 1

Explanation

• The union method merges two subsets by comparing their ranks and attaching the smaller tree under the larger tree.

Step 4: Putting It All Together

• Initialize your Union-Find structure and perform a series of union and find operations to demonstrate connectivity.

Code Example

uf = UnionFind(10)
uf.union(1, 2)
uf.union(2, 3)

print(uf.find(1))  # Output: root of the set containing 1
print(uf.find(3))  # Output: root of the set containing 3

Common Pitfall

• Forgetting to use path compression can lead to inefficient operations, especially in large datasets.

Conclusion

In this tutorial, we covered the Union-Find data structure, focusing on its essential operations: Find and Union. We provided practical implementations with optimizations for efficiency. You can use this structure in various applications, including network connectivity problems and clustering algorithms.

Next Steps

• Practice implementing Union-Find with different datasets.
• Explore its applications in graph algorithms, such as Kruskal's algorithm for finding the minimum spanning tree.