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.