并查集：连通性检测与冗余连接

并查集模板（路径压缩 + 按秩合并）

class UnionFind {
    private int[] parent, 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;
    }
    // 路径压缩（递归）
    public int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    // 按秩合并
    public boolean union(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        if (rank[px] < rank[py]) { int tmp = px; px = py; py = tmp; }
        parent[py] = px;
        if (rank[px] == rank[py]) rank[px]++;
        components--;
        return true;
    }
    public int getComponents() { return components; }
    public boolean connected(int x, int y) { return find(x) == find(y); }
}

朋友圈（LeetCode 547 - 省份数量）

将矩阵看作邻接矩阵，统计连通分量数：

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();
}

冗余连接（LeetCode 684）

找使图构成环的那条边（树中已连通的两点再连就会成环）：

public int[] findRedundantConnection(int[][] edges) {
    int n = edges.length;
    UnionFind uf = new UnionFind(n + 1);
    for (int[] edge : edges) {
        if (!uf.union(edge[0], edge[1])) return edge; // 已连通，即为冗余边
    }
    return new int[0];
}

账户合并（LeetCode 721）

将共享邮箱的账户合并（以第一个邮箱为代表），并查集将邮箱和账户 ID 关联：

public List<List<String>> accountsMerge(List<List<String>> accounts) {
    Map<String, Integer> emailToId = 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 (emailToId.containsKey(email)) uf.union(i, emailToId.get(email));
            else emailToId.put(email, i);
        }
    }
    // 按根节点分组
    Map<Integer, List<String>> groups = new HashMap<>();
    for (String email : emailToId.keySet()) {
        int root = uf.find(emailToId.get(email));
        groups.computeIfAbsent(root, k -> new ArrayList<>()).add(email);
    }
    List<List<String>> result = new ArrayList<>();
    for (Map.Entry<Integer, List<String>> e : groups.entrySet()) {
        List<String> emails = e.getValue();
        Collections.sort(emails);
        emails.add(0, emailToName.get(emails.get(0)));
        result.add(emails);
    }
    return result;
}

总结