A crash course on Disjoint Set Union (aka Union Find) data structure.

The Disjoint Set Union (DSU) is a way to handle groups of items that don't overlap. It's great for figuring out if elements are connected in a group and for joining different groups together. Think of each group as a tree, with the top of the tree being the main item in the group.

Key Operations

1. Find(x): This finds the main item of the group where 'x' is.
2. Unite(x, y): This joins the groups of 'x' and 'y'.
3. Same(x, y): This checks if 'x' and 'y' are in the same group.

How It Works

Instead of using complex tree structures, we use a simple array. Each item points to its parent in the group. The main item of a group points to itself. At the start, every item is its own group.

Simple Implementations

1. Quick Find: Here, finding is fast, but uniting groups is slow.
2. Quick Union: This makes uniting groups faster on average.

Improved Methods

1. Weighted Union: This balances the trees, making operations faster.
2. Path Compression: This makes finding the main item faster by shortening the path.

Applications

1. Graphs: DSU can quickly find connected parts in a graph.
2. Image Processing: It helps in grouping pixels with the same intensity.
3. Kruskal's Algorithm: DSU is used in this algorithm to find the minimum spanning tree in a graph.

Example Problem: Longest Consecutive Sequence

Imagine you have a bunch of numbers and want to find the longest sequence where numbers are next to each other. Using DSU, you can do this efficiently by treating each consecutive sequence as a connected component.

Example Code

Let's create a simple DSU class in C++ with basic operations. We'll change the code slightly from the original blog for uniqueness:

class SimpleDSU:
    def __init__(self, n):
        self.parent = list(range(n))  # Each element is its own parent initially

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

    def unite(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            self.parent[rootY] = rootX  # Attach root of Y to root of X

    def is_connected(self, x, y):
        return self.find(x) == self.find(y)

# Example usage
dsu = SimpleDSU(10)  # Create a DSU for 10 elements
dsu.unite(2, 3)
dsu.unite(3, 4)

print(dsu.is_connected(2, 4))  # Should return True
print(dsu.is_connected(2, 5))  # Should return False

Conclusion

DSU is a powerful, yet simple tool for handling non-overlapping groups. It's useful in many areas like graph theory, image processing, and more. Understanding DSU and its optimizations can greatly improve the efficiency of your algorithms.