What is the Union-Find data structure?

The Union-Find or Disjoint Set Union (DSU) data structure is used to keep track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets. It provides two main operations: 'find' to determine which subset an element belongs to, and 'union' to merge two subsets.

What are the key optimizations for Union-Find?

The two key optimizations for the Union-Find data structure are 'Path Compression' and 'Union by Rank/Size'. Path compression flattens the structure of the tree during 'find' operations, and union by rank/size ensures the shorter tree is merged under the taller one, keeping the trees balanced.

Data Structures

Union-Find (Disjoint Set Union)

A specialized data structure that efficiently tracks a partition of a set into disjoint subsets, crucial for problems involving connectivity and cycle detection in graphs.

Union-Find in Python

Here is a Python implementation of the Union-Find data structure with path compression and union by size optimizations.

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

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

    def union(self, i, j):
        root_i = self.find(i)
        root_j = self.find(j)
        if root_i != root_j:
            # Union by size
            if self.size[root_i] < self.size[root_j]:
                root_i, root_j = root_j, root_i
            self.parent[root_j] = root_i
            self.size[root_i] += self.size[root_j]

AI Coach Hint: The combination of path compression and union by size/rank makes the Union-Find data structure nearly constant on average for each operation, making it extremely efficient for problems like detecting cycles in an undirected graph or Kruskal's algorithm.