Union-Find Patterns: Complete Reference¶

class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))  # Initially, each node is its own parent
        self.rank = [0] * n           # Rank (tree depth upper bound)

    def find(self, x: int) -> int:
        """Find with path compression."""
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x: int, y: int) -> bool:
        """Union by rank. Returns True if union performed (different sets)."""
        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
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

# Without path compression:
#     1           After find(5): 1→2→3→4→5
#    /            Every find traverses full chain: O(n)
#   2
#  /
# 3
#  \
#   4
#    \
#     5

# With path compression:
#       1         After find(5): All nodes point to root
#    / | \ \      Subsequent finds: O(1)
#   2  3  4  5

# Without rank: Tree can become a linked list (O(n) per operation)
# With rank: Tree height stays O(log n)

# Union by rank: Always attach shorter tree under taller tree
# This keeps tree balanced

# Check if connected
def connected(self, x: int, y: int) -> bool:
    return self.find(x) == self.find(y)

# Count connected components
def count_components(self) -> int:
    return sum(1 for i, p in enumerate(self.parent) if self.find(i) == i)

# Get size of component (need to track sizes)
def __init__(self, n: int):
    self.parent = list(range(n))
    self.rank = [0] * n
    self.size = [1] * n  # Track component sizes

def union(self, x: int, y: int) -> bool:
    px, py = self.find(x), self.find(y)
    if px == py:
        return False
    if self.rank[px] < self.rank[py]:
        px, py = py, px
    self.parent[py] = px
    self.size[px] += self.size[py]  # Update size
    if self.rank[px] == self.rank[py]:
        self.rank[px] += 1
    return True

# Pattern: union_find_connected_components
# See: docs/patterns/union_find/templates.md Section 1 (Base Template)

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        """
        Count number of provinces (connected components).

        Key Insight:
        - Start with n components (each city is its own province)
        - Each successful union reduces count by 1
        - Final count = number of provinces

        Why Union-Find over DFS?
        - Same complexity O(n²) for this problem
        - Union-Find is more natural for connectivity queries
        - Easier to extend for dynamic edge additions
        """
        n = len(isConnected)
        parent = list(range(n))
        rank = [0] * n

        def find(x: int) -> int:
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(x: int, y: int) -> bool:
            px, py = find(x), find(y)
            if px == py:
                return False
            if rank[px] < rank[py]:
                px, py = py, px
            parent[py] = px
            if rank[px] == rank[py]:
                rank[px] += 1
            return True

        components = n
        for i in range(n):
            for j in range(i + 1, n):  # Only upper triangle (symmetric)
                if isConnected[i][j] == 1:
                    if union(i, j):
                        components -= 1

        return components

# Pattern: union_find_cycle_detection
# See: docs/patterns/union_find/templates.md Section 2

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        """
        Find the edge that creates a cycle.

        Key Insight:
        - Process edges in order
        - Union returns False if nodes already connected
        - That edge is redundant (creates a cycle)

        Why this works:
        - In a tree with n nodes, there are n-1 edges
        - Adding one more edge creates exactly one cycle
        - The edge connecting already-connected nodes is redundant
        """
        n = len(edges)
        parent = list(range(n + 1))  # 1-indexed
        rank = [0] * (n + 1)

        def find(x: int) -> int:
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(x: int, y: int) -> bool:
            px, py = find(x), find(y)
            if px == py:
                return False  # Cycle detected!
            if rank[px] < rank[py]:
                px, py = py, px
            parent[py] = px
            if rank[px] == rank[py]:
                rank[px] += 1
            return True

        for u, v in edges:
            if not union(u, v):
                return [u, v]

        return []  # Should never reach here

# Pattern: union_find_equivalence_grouping
# See: docs/patterns/union_find/templates.md Section 3

class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        """
        Merge accounts sharing common emails.

        Key Insight:
        - Map each email to first account index that has it
        - If email seen before, union current account with previous account
        - Collect emails by component root

        Why Union-Find?
        - Handles transitive relationships naturally
        - A shares email with B, B shares with C → A, B, C all merge
        """
        from collections import defaultdict

        n = len(accounts)
        parent = list(range(n))
        rank = [0] * n

        def find(x: int) -> int:
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(x: int, y: int) -> None:
            px, py = find(x), find(y)
            if px == py:
                return
            if rank[px] < rank[py]:
                px, py = py, px
            parent[py] = px
            if rank[px] == rank[py]:
                rank[px] += 1

        # Map email to first account index
        email_to_account: dict[str, int] = {}

        for i, account in enumerate(accounts):
            for email in account[1:]:  # Skip name
                if email in email_to_account:
                    # Union this account with account that has same email
                    union(i, email_to_account[email])
                else:
                    email_to_account[email] = i

        # Collect emails by root
        root_to_emails: dict[int, set[str]] = defaultdict(set)
        for email, account_idx in email_to_account.items():
            root = find(account_idx)
            root_to_emails[root].add(email)

        # Build result
        result: list[list[str]] = []
        for root, emails in root_to_emails.items():
            name = accounts[root][0]
            result.append([name] + sorted(emails))

        return result

# Pattern: union_find_network_connectivity
# See: docs/patterns/union_find/templates.md Section 4

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        """
        Minimum cables to move to connect all computers.

        Key Insight:
        - Need at least n-1 edges to connect n nodes
        - Redundant edges (forming cycles) can be moved
        - Count components and check if enough redundant edges

        Algorithm:
        1. If edges < n-1: impossible (-1)
        2. Count components using Union-Find
        3. Need (components - 1) moves to connect all
        """
        if len(connections) < n - 1:
            return -1  # Not enough cables

        parent = list(range(n))
        rank = [0] * n

        def find(x: int) -> int:
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(x: int, y: int) -> bool:
            px, py = find(x), find(y)
            if px == py:
                return False  # Redundant edge
            if rank[px] < rank[py]:
                px, py = py, px
            parent[py] = px
            if rank[px] == rank[py]:
                rank[px] += 1
            return True

        components = n
        for a, b in connections:
            if union(a, b):
                components -= 1

        return components - 1

# Not enough edges
n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]
# 4 edges < 5 needed → return -1

# Already connected
n = 4, connections = [[0,1],[0,2],[1,2],[1,3],[2,3]]
# 1 component → return 0

# Worst case: all isolated
n = 4, connections = []
# 0 edges < 3 needed → return -1

# Pattern: union_find_constraint_satisfaction
# See: docs/patterns/union_find/templates.md Section 5

class Solution:
    def equationsPossible(self, equations: List[str]) -> bool:
        """
        Check if all equations can be satisfied.

        Key Insight:
        - Process '==' first: union all equal variables
        - Then check '!=': must be in different components
        - If any '!=' has variables in same component → unsatisfiable

        Why two passes?
        - Equality is transitive (a==b, b==c → a==c)
        - Must build all equality relationships before checking inequality
        """
        parent = list(range(26))  # 26 lowercase letters
        rank = [0] * 26

        def find(x: int) -> int:
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(x: int, y: int) -> None:
            px, py = find(x), find(y)
            if px == py:
                return
            if rank[px] < rank[py]:
                px, py = py, px
            parent[py] = px
            if rank[px] == rank[py]:
                rank[px] += 1

        # Pass 1: Process all equalities
        for eq in equations:
            if eq[1] == '=':  # "a==b"
                x = ord(eq[0]) - ord('a')
                y = ord(eq[3]) - ord('a')
                union(x, y)

        # Pass 2: Check all inequalities
        for eq in equations:
            if eq[1] == '!':  # "a!=b"
                x = ord(eq[0]) - ord('a')
                y = ord(eq[3]) - ord('a')
                if find(x) == find(y):
                    return False  # Contradiction!

        return True

# Self-inequality
equations = ["a!=a"]
# Pass 1: nothing
# Pass 2: find(a) == find(a) → False

# Self-equality (trivially true)
equations = ["a==a"]
# Pass 1: union(a, a) → no-op
# Pass 2: nothing
# Output: True

# Disjoint groups with inequality
equations = ["a==b", "c==d", "a!=d"]
# Pass 1: {a,b}, {c,d}
# Pass 2: find(a)≠find(d) → True

# ✓ USE Union-Find when:
# - Multiple connectivity queries after building
# - Dynamic edge additions (but not deletions!)
# - Only need "are X and Y connected?" not "what's the path?"
# - Detecting cycles during graph construction

# ✗ DON'T USE Union-Find when:
# - Need to find actual path between nodes
# - Need to handle edge deletions
# - Single connectivity query (DFS is simpler)
# - Need shortest path (BFS is better)

# BASIC UNION-FIND (most problems)
def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(x, y):
    px, py = find(x), find(y)
    if px == py: return False
    parent[py] = px
    return True

# WITH RANK (balanced trees)
def union_by_rank(x, y):
    px, py = find(x), find(y)
    if px == py: return False
    if rank[px] < rank[py]: px, py = py, px
    parent[py] = px
    if rank[px] == rank[py]: rank[px] += 1
    return True

# WITH SIZE TRACKING
def union_with_size(x, y):
    px, py = find(x), find(y)
    if px == py: return False
    if size[px] < size[py]: px, py = py, px
    parent[py] = px
    size[px] += size[py]
    return True

# 1-indexed nodes (LC 684)
parent = list(range(n + 1))  # Extra slot for 1-indexing

# Character indices (LC 990)
x = ord(char) - ord('a')  # 'a'->0, 'b'->1, etc.

# String to index mapping (LC 721)
string_to_idx = {}
for i, s in enumerate(strings):
    if s not in string_to_idx:
        string_to_idx[s] = len(string_to_idx)

# Coordinate to index (grid problems)
idx = row * cols + col

class UnionFind:
    """Standard Union-Find with path compression and union by rank."""

    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.components = n

    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x: int, y: int) -> bool:
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        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.components -= 1
        return True

    def connected(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)

def solve(n: int, edges: List[List[int]]) -> int:
    parent = list(range(n))
    rank = [0] * n

    def find(x: int) -> int:
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(x: int, y: int) -> bool:
        px, py = find(x), find(y)
        if px == py:
            return False
        if rank[px] < rank[py]:
            px, py = py, px
        parent[py] = px
        if rank[px] == rank[py]:
            rank[px] += 1
        return True

    # Use find() and union() here

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

    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x: int, y: int) -> bool:
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        # Union by size
        if self.size[px] < self.size[py]:
            px, py = py, px
        self.parent[py] = px
        self.size[px] += self.size[py]
        return True

    def get_size(self, x: int) -> int:
        return self.size[self.find(x)]

def find_redundant_edge(edges: List[List[int]]) -> List[int]:
    n = len(edges)
    parent = list(range(n + 1))

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    for u, v in edges:
        pu, pv = find(u), find(v)
        if pu == pv:
            return [u, v]  # Cycle found!
        parent[pv] = pu

    return []

def check_equations(equations: List[str]) -> bool:
    parent = list(range(26))

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    # Pass 1: Union equals
    for eq in equations:
        if eq[1] == '=':
            x, y = ord(eq[0]) - ord('a'), ord(eq[3]) - ord('a')
            parent[find(y)] = find(x)

    # Pass 2: Check not-equals
    for eq in equations:
        if eq[1] == '!':
            x, y = ord(eq[0]) - ord('a'), ord(eq[3]) - ord('a')
            if find(x) == find(y):
                return False

    return True