Classic Union-Find Problems

1. Number of Islands

def numIslands(grid):
    """Count islands using Union-Find"""
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    uf = UnionFind(rows * cols)

    def index(r, c):
        return r * cols + c

    # Union adjacent land cells
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                for dr, dc in [(0,1), (1,0)]:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                        uf.union(index(r, c), index(nr, nc))

    # Count unique roots of land cells
    return len(set(uf.find(index(r, c))
                   for r in range(rows)
                   for c in range(cols)
                   if grid[r][c] == '1'))

2. Redundant Connection

def findRedundantConnection(edges):
    """Find edge that creates cycle"""
    uf = UnionFind(len(edges) + 1)

    for u, v in edges:
        if not uf.union(u, v):
            return [u, v]  # This edge creates cycle

    return []

3. Accounts Merge

def accountsMerge(accounts):
    """Merge accounts with common emails"""
    from collections import defaultdict

    uf = UnionFind(len(accounts))
    email_to_id = {}

    # Build union-find
    for i, account in enumerate(accounts):
        for email in account[1:]:
            if email in email_to_id:
                uf.union(i, email_to_id[email])
            else:
                email_to_id[email] = i

    # Group emails by root
    root_to_emails = defaultdict(set)
    for email, idx in email_to_id.items():
        root = uf.find(idx)
        root_to_emails[root].add(email)

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

    return result

4. Smallest String With Swaps

def smallestStringWithSwaps(s, pairs):
    """Find lexicographically smallest string after swaps"""
    from collections import defaultdict

    n = len(s)
    uf = UnionFind(n)

    # Union indices that can be swapped
    for i, j in pairs:
        uf.union(i, j)

    # Group indices by root
    groups = defaultdict(list)
    for i in range(n):
        root = uf.find(i)
        groups[root].append(i)

    # Sort characters in each group
    result = list(s)
    for indices in groups.values():
        chars = sorted([s[i] for i in indices])
        for i, char in zip(sorted(indices), chars):
            result[i] = char

    return ''.join(result)

5. Satisfiability of Equality Equations

def equationsPossible(equations):
    """Check if equations are satisfiable"""
    uf = UnionFind(26)

    # Process equality equations first
    for eq in equations:
        if eq[1] == '=':
            x = ord(eq[0]) - ord('a')
            y = ord(eq[3]) - ord('a')
            uf.union(x, y)

    # Check inequality equations
    for eq in equations:
        if eq[1] == '!':
            x = ord(eq[0]) - ord('a')
            y = ord(eq[3]) - ord('a')
            if uf.find(x) == uf.find(y):
                return False

    return True

Common Patterns

1. Connectivity: Check if elements are connected
2. Cycle Detection: Union returns false when cycle found
3. Grouping: Group elements by their root
4. Dynamic Connectivity: Add/remove connections efficiently

Key Takeaway

Union-Find excels at managing relationships between elements. The pattern is: build the union-find structure by processing connections, then query it to answer connectivity questions or group related elements.