Union-Find: Connectivity Detection and Redundant Connections

Union-Find Template (Path Compression + Union by Rank)

class UnionFind {
    private final int[] parent;
    private final int[] rank;
    private int components;

    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        components = n;
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    // Path Compression (Recursive)
    public int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }

    // Union by Rank
    public boolean union(int x, int y) {
        int rootX = find(x), rootY = find(y);
        if (rootX == rootY) return false;
        
        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;
    }

    public int getComponents() { return components; }
    public boolean connected(int x, int y) { return find(x) == find(y); }
}

Number of Provinces (LeetCode 547)

Given an adjacency matrix, determine the total number of connected components.

public int findCircleNum(int[][] isConnected) {
    int n = isConnected.length;
    UnionFind uf = new UnionFind(n);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (isConnected[i][j] == 1) {
                uf.union(i, j);
            }
        }
    }
    return uf.getComponents();
}

Redundant Connection (LeetCode 684)

Identify the edge that creates a cycle in a graph. In a tree, any edge added between two already-connected nodes is redundant.

public int[] findRedundantConnection(int[][] edges) {
    int n = edges.length;
    UnionFind uf = new UnionFind(n + 1);
    for (int[] edge : edges) {
        // If union() returns false, it means the two nodes were already connected.
        // This edge is the cycle-forming edge.
        if (!uf.union(edge[0], edge[1])) return edge;
    }
    return new int[0];
}

Accounts Merge (LeetCode 721)

Merge accounts that share email addresses. We treat account indices as Union-Find nodes and emails as links between these indices.

public List<List<String>> accountsMerge(List<List<String>> accounts) {
    Map<String, Integer> emailToAccountId = new HashMap<>();
    Map<String, String> emailToName = new HashMap<>();
    int n = accounts.size();
    UnionFind uf = new UnionFind(n);
    
    for (int i = 0; i < n; i++) {
        String name = accounts.get(i).get(0);
        for (int j = 1; j < accounts.get(i).size(); j++) {
            String email = accounts.get(i).get(j);
            emailToName.put(email, name);
            if (emailToAccountId.containsKey(email)) {
                // Shared email found: union the account indices
                uf.union(i, emailToAccountId.get(email));
            } else {
                emailToAccountId.put(email, i);
            }
        }
    }
    
    // Group all emails by their account's Union-Find root
    Map<Integer, List<String>> groups = new HashMap<>();
    for (String email : emailToAccountId.keySet()) {
        int root = uf.find(emailToAccountId.get(email));
        groups.computeIfAbsent(root, k -> new ArrayList<>()).add(email);
    }
    
    // Format the final results
    List<List<String>> result = new ArrayList<>();
    for (List<String> emails : groups.values()) {
        Collections.sort(emails);
        emails.add(0, emailToName.get(emails.get(0)));
        result.add(emails);
    }
    return result;
}

Summary Table