Union Find

What is Union-Find?

Union-Find (also called Disjoint Set Union or DSU) is a data structure that tracks elements partitioned into disjoint (non-overlapping) sets. It supports two operations:

1. Find: Determine which set an element belongs to
2. Union: Merge two sets into one

Key Concepts

Initial State:     After Union(0,1):   After Union(2,3):   After Union(1,3):
{0} {1} {2} {3}    {0,1} {2} {3}       {0,1} {2,3}         {0,1,2,3}

Represented as tree:
  0   1   2   3      0       2           0       
  |   |   |   |      |       |           |       
  -   -   -   -      1       3           1       
                                      / \n                                     2   3

Basic Implementation

public class UnionFind {
    private int[] parent;
    private int[] rank;
    private int components;
    
    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        components = n;
        
        // Each element is its own parent initially
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    
    // Find with path compression
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // Path compression
        }
        return parent[x];
    }
    
    // Union by rank
    public boolean union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        
        if (rootX == rootY) {
            return false; // Already in same set (cycle detected!)
        }
        
        // Attach smaller tree under larger tree
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        
        components--;
        return true;
    }
    
    // Check if two elements are in same set
    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }
    
    // Get number of connected components
    public int getComponents() {
        return components;
    }
}

Why Path Compression and Union by Rank?

Without optimizations:

• Tree can become tall and skewed
• Find operation: O(n) worst case

With optimizations:

• Tree stays nearly flat
• Find operation: O(α(n)) ≈ O(1) amortized
• α(n) is the inverse Ackermann function (practically constant)

Time Complexity

Operation	Without Optimization	With Optimization
Find	O(n)	O(α(n)) ≈ O(1)
Union	O(n)	O(α(n)) ≈ O(1)
Connected	O(n)	O(α(n)) ≈ O(1)

Visual Example of Path Compression

Before find(3):     After find(3):
    0                   0
    |                  /|\
    1                 1 2 3
    |
    2
    |
    3

All nodes now point directly to root!

Common Applications

1. Dynamic Connectivity

Determine if two elements are connected as edges are added.

// Example: Number of connected components
public int countComponents(int n, int[][] edges) {
    UnionFind uf = new UnionFind(n);
    for (int[] edge : edges) {
        uf.union(edge[0], edge[1]);
    }
    return uf.getComponents();
}

2. Cycle Detection in Undirected Graph

public boolean hasCycle(int n, int[][] edges) {
    UnionFind uf = new UnionFind(n);
    
    for (int[] edge : edges) {
        if (!uf.union(edge[0], edge[1])) {
            return true; // Cycle detected!
        }
    }
    return false;
}

3. Redundant Connection

// Find edge that creates cycle
public int[] findRedundantConnection(int[][] edges) {
    UnionFind uf = new UnionFind(edges.length + 1);
    
    for (int[] edge : edges) {
        if (!uf.union(edge[0], edge[1])) {
            return edge; // This edge creates cycle
        }
    }
    return new int[0];
}

4. Accounts Merge

public List<List<String>> accountsMerge(List<List<String>> accounts) {
    Map<String, Integer> emailToId = new HashMap<>();
    Map<String, String> emailToName = new HashMap<>();
    int id = 0;
    
    UnionFind uf = new UnionFind(accounts.size() * 10);
    
    for (List<String> account : accounts) {
        String name = account.get(0);
        for (int i = 1; i < account.size(); i++) {
            String email = account.get(i);
            emailToName.put(email, name);
            if (!emailToId.containsKey(email)) {
                emailToId.put(email, id++);
            }
            uf.union(emailToId.get(account.get(1)), emailToId.get(email));
        }
    }
    
    Map<Integer, List<String>> merged = new HashMap<>();
    for (String email : emailToId.keySet()) {
        int root = uf.find(emailToId.get(email));
        merged.computeIfAbsent(root, k -> new ArrayList<>()).add(email);
    }
    
    List<List<String>> result = new ArrayList<>();
    for (List<String> emails : merged.values()) {
        Collections.sort(emails);
        List<String> account = new ArrayList<>();
        account.add(emailToName.get(emails.get(0)));
        account.addAll(emails);
        result.add(account);
    }
    
    return result;
}

5. Surrounded Regions (with Union-Find)

public void solve(char[][] board) {
    int rows = board.length, cols = board[0].length;
    UnionFind uf = new UnionFind(rows * cols + 1);
    int dummy = rows * cols;
    
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (board[r][c] == 'O') {
                int cell = r * cols + c;
                // Connect boundary O's to dummy
                if (r == 0 || r == rows-1 || c == 0 || c == cols-1) {
                    uf.union(cell, dummy);
                }
                // Connect to adjacent O's
                if (r > 0 && board[r-1][c] == 'O') uf.union(cell, (r-1)*cols + c);
                if (c > 0 && board[r][c-1] == 'O') uf.union(cell, r*cols + (c-1));
            }
        }
    }
    
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (board[r][c] == 'O' && !uf.connected(r * cols + c, dummy)) {
                board[r][c] = 'X';
            }
        }
    }
}

Problem Pattern Recognition

Problem	Union-Find Usage
Connected Components	Count components after unions
Cycle Detection	If union returns false, cycle exists
Redundant Connection	Find edge that creates cycle
Accounts Merge	Group emails by account
Similar String Groups	Group equivalent strings
Number of Islands II	Dynamic island counting