Disjoint set union

class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.size = [1] * n  # Track size of each set
        self.components = n  # Track number of components
    
    def find(self, x):
        # Path compression
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False  # Already in same set
        
        # Union by rank
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        self.size[px] += self.size[py]
        
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        
        self.components -= 1
        return True
    
    def connected(self, x, y):
        return self.find(x) == self.find(y)
    
    def get_size(self, x):
        return self.size[self.find(x)]

class PathSplittingDSU:
    def __init__(self, n):
        self.parent = list(range(n))
    
    def find(self, x):
        # Path splitting
        while self.parent[x] != x:
            next_parent = self.parent[self.parent[x]]
            self.parent[x] = next_parent
            x = next_parent
        return x

class PathHalvingDSU:
    def __init__(self, n):
        self.parent = list(range(n))
    
    def find(self, x):
        # Path halving
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

class WeightedQuickUnion:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
    
    def find(self, x):
        while self.parent[x] != x:
            x = self.parent[x]
        return x
    
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return
        
        # Always attach smaller tree under root of larger tree
        if self.size[px] < self.size[py]:
            self.parent[px] = py
            self.size[py] += self.size[px]
        else:
            self.parent[py] = px
            self.size[px] += self.size[py]

def handle_single(self, x):
    return self.parent[x] == x and self.size[x] == 1

def union_safe(self, x, y):
    if x == y:
        return False  # Cannot union element with itself
    return self.union(x, y)

def validate_element(self, x):
    if not 0 <= x < len(self.parent):
        raise ValueError(f"Element {x} out of range")

def find_iterative(self, x):
    # Find root
    root = x
    while self.parent[root] != root:
        root = self.parent[root]
    
    # Compress path
    while x != root:
        next_parent = self.parent[x]
        self.parent[x] = root
        x = next_parent
    
    return root

class RankBalancedDSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.max_rank = 0
    
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return
        
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
            self.max_rank = max(self.max_rank, self.rank[px])

class CompactDSU:
    def __init__(self, n):
        # Use a single array for both parent and rank
        # Higher 16 bits for rank, lower 16 bits for parent
        self.data = list(range(n))
    
    def get_parent(self, x):
        return self.data[x] & 0xFFFF
    
    def get_rank(self, x):
        return self.data[x] >> 16
    
    def set_parent(self, x, parent):
        self.data[x] = (self.get_rank(x) << 16) | parent
    
    def set_rank(self, x, rank):
        self.data[x] = (rank << 16) | self.get_parent(x)

class DynamicDSU:
    def __init__(self):
        self.parent = {}
        self.rank = {}
    
    def make_set(self, x):
        if x not in self.parent:
            self.parent[x] = x
            self.rank[x] = 0
    
    def find(self, x):
        if x not in self.parent:
            self.make_set(x)
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

def batch_union(self, pairs):
    # Sort pairs to optimize cache usage
    pairs.sort()
    for x, y in pairs:
        self.union(x, y)

class SizeOptimizedDSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
    
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return
        
        # Always merge smaller component into larger
        if self.size[px] < self.size[py]:
            self.parent[px] = py
            self.size[py] += self.size[px]
        else:
            self.parent[py] = px
            self.size[px] += self.size[py]

# Wrong
def find_wrong(self, x):
    while self.parent[x] != x:
        x = self.parent[x]
    return x

# Correct
def find_correct(self, x):
    if self.parent[x] != x:
        self.parent[x] = self.find_correct(self.parent[x])
    return self.parent[x]

# Wrong
def union_wrong(self, x, y):
    px, py = self.find(x), self.find(y)
    if px == py:
        return
    self.parent[py] = px
    self.rank[px] += 1  # Always incrementing rank

# Correct
def union_correct(self, x, y):
    px, py = self.find(x), self.find(y)
    if px == py:
        return
    if self.rank[px] < self.rank[py]:
        px, py = py, px
    self.parent[py] = px
    if self.rank[px] == self.rank[py]:
        self.rank[px] += 1

# Wrong
def union_no_count(self, x, y):
    px, py = self.find(x), self.find(y)
    if px == py:
        return
    self.parent[py] = px  # Lost track of component count

# Correct
def union_with_count(self, x, y):
    px, py = self.find(x), self.find(y)
    if px == py:
        return
    self.parent[py] = px
    self.components -= 1  # Track components