Ruigu Electronic

class UnionFind:
    """
    Union-Find (Disjoint Set Union, DSU) data structure with path compression and union by rank.
    Supports numeric elements (0-indexed or arbitrary integers).
    """
    def __init__(self, size):
        """
        Initialize Union-Find with `size` elements (0 to size-1).
        Args:
            size (int): Number of elements to manage (must be ≥ 1).
        """
        if size < 1:
            raise ValueError("Size must be at least 1")
        
        # parent[i] = parent of element i (initially, each element is its own parent)
        self.parent = list(range(size))
        
        # rank[i] = upper bound of the height of the tree rooted at i (for union by rank)
        self.rank = [0] * size
        
        # Optional: Track size of each set (alternative to rank for union by size)
        self.size = [1] * size
    
    def find(self, x):
        """
        Find the root of element x with path compression.
        Args:
            x (int): Element to find (must be between 0 and size-1).
        Returns:
            int: Root of the set containing x.
        """
        # Validate input
        if x < 0 or x >= len(self.parent):
            raise IndexError("Element out of bounds")
        
        # Path compression: Make x's parent point directly to the root
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # Recursively find root and update parent
        return self.parent[x]
    
    def union(self, x, y):
        """
        Merge the sets containing elements x and y using union by rank.
        Args:
            x (int): First element (0 ≤ x < size).
            y (int): Second element (0 ≤ y < size).
        Returns:
            bool: True if sets were merged (x and y were in different sets), False otherwise (already in the same set).
        """
        # Find roots of x and y
        root_x = self.find(x)
        root_y = self.find(y)
        
        # If already in the same set, do nothing
        if root_x == root_y:
            return False
        
        # Union by rank: Attach smaller rank tree to root of larger rank tree
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
            self.size[root_y] += self.size[root_x]  # Update size of root_y's set
        else:
            self.parent[root_y] = root_x
            self.size[root_x] += self.size[root_y]  # Update size of root_x's set
            
            # If ranks are equal, increment rank of the new root
            if self.rank[root_x] == self.rank[root_y]:
                self.rank[root_x] += 1
        
        return True
    
    def connected(self, x, y):
        """
        Check if elements x and y are in the same set.
        Args:
            x (int): First element.
            y (int): Second element.
        Returns:
            bool: True if x and y are in the same set, False otherwise.
        """
        return self.find(x) == self.find(y)
    
    def get_set_size(self, x):
        """
        Get the size of the set containing element x.
        Args:
            x (int): Element to query.
        Returns:
            int: Size of the set.
        """
        root = self.find(x)
        return self.size[root]
    
    def get_num_sets(self):
        """
        Get the number of disjoint sets currently managed.
        Returns:
            int: Number of disjoint sets.
        """
        # Count elements that are their own parent (roots)
        return sum(1 for i in range(len(self.parent)) if self.parent[i] == i)

# Test the Union-Find implementation
if __name__ == "__main__":
    # Initialize Union-Find with 6 elements (0-5)
    uf = UnionFind(6)
    print("Initial number of sets:", uf.get_num_sets())  # Output: 6
    
    # Merge sets
    uf.union(0, 1)
    uf.union(1, 2)
    uf.union(3, 4)
    print("\nAfter merging (0-1-2) and (3-4):")
    print("Number of sets:", uf.get_num_sets())  # Output: 3 (sets: {0,1,2}, {3,4}, {5})
    print("0 and 2 are connected?", uf.connected(0, 2))  # Output: True
    print("2 and 3 are connected?", uf.connected(2, 3))  # Output: False
    print("Size of set containing 1:", uf.get_set_size(1))  # Output: 3
    
    # Merge more sets
    uf.union(2, 3)
    uf.union(4, 5)
    print("\nAfter merging (0-1-2-3-4) and (5):")
    print("Number of sets:", uf.get_num_sets())  # Output: 1 (all elements connected)
    print("0 and 5 are connected?", uf.connected(0, 5))  # Output: True
    print("Size of set containing 5:", uf.get_set_size(5))  # Output: 6

Initial number of sets: 6

After merging (0-1-2) and (3-4):
Number of sets: 3
0 and 2 are connected? True
2 and 3 are connected? False
Size of set containing 1: 3

After merging (0-1-2-3-4) and (5):
Number of sets: 1
0 and 5 are connected? True
Size of set containing 5: 6