Union Find Class

class UnionFind:
    """
    Union-Find (Disjoint Set Union) class to group elements into clusters.

    Time Complexity: O(α(n)), where α is the Inverse Ackermann function, very slow-growing.
    Space Complexity: O(n), where n is the number of elements.
    """

    def __init__(self):
        self.parent = {}
        self.rank = {}

    def find(self, item):
        """Find the root representative of the item."""
        if self.parent[item] != item:
            self.parent[item] = self.find(self.parent[item])  # Path compression
        return self.parent[item]

    def union(self, item1, item2):
        """Union the sets that contain item1 and item2."""
        root1 = self.find(item1)
        root2 = self.find(item2)
        if root1 != root2:
            # Union by rank
            if self.rank[root1] > self.rank[root2]:
                self.parent[root2] = root1
            elif self.rank[root1] < self.rank[root2]:
                self.parent[root1] = root2
            else:
                self.parent[root2] = root1
                self.rank[root1] += 1

    def add(self, item):
        """Add an item to the union-find structure."""
        if item not in self.parent:
            self.parent[item] = item
            self.rank[item] = 0