并查集

什么是并查集？

并查集（Union-Find / Disjoint Set Union） 是一种数据结构，用于高效地解决动态连通性问题：判断两个元素是否属于同一集合，以及合并两个集合。

核心操作：

• find(x) — 查找 x 所在集合的根节点（"代表元"）
• union(x, y) — 合并 x 和 y 所在的集合

按秩合并 + 路径压缩

两种优化都加上，可以实现接近 O(1)（均摊 O(α(n))，α 是阿克曼逆函数）的操作。

class UnionFind {
    private int[] parent;
    private int[] rank;    // 按秩合并：rank[i] 是 i 所在树的高度估计
    private int count;     // 连通分量数量

    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        count = 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];
    }

    // 按秩合并：将rank小的树接到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]++;
        }
        count--;
        return true;
    }

    public boolean connected(int x, int y) { return find(x) == find(y); }
    public int getCount() { return count; }
}

经典例题 1：岛屿数量（并查集版）

int numIslands(char[][] grid) {
    int rows = grid.length, cols = grid[0].length;
    UnionFind uf = new UnionFind(rows * cols);
    int water = 0;  // 水格数量
    int[] dr = {0, 1}, dc = {1, 0};  // 只需检查右和下
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == '0') { water++; continue; }
            for (int d = 0; d < 2; d++) {
                int nr = r + dr[d], nc = c + dc[d];
                if (nr < rows && nc < cols && grid[nr][nc] == '1') {
                    uf.union(r * cols + c, nr * cols + nc);
                }
            }
        }
    }
    return uf.getCount() - water;  // 减去水格子
}

经典例题 2：冗余连接

在无向图中，找到一条可以删除的边，使得剩余图仍是树（无环连通图）。

int[] findRedundantConnection(int[][] edges) {
    int n = edges.length;
    UnionFind uf = new UnionFind(n + 1);  // 节点编号 1 到 n
    for (int[] e : edges) {
        if (!uf.union(e[0], e[1])) {
            return e;  // 合并失败 = 已连通 = 这条边是冗余的
        }
    }
    return new int[0];
}

关键理解：若添加边 (u, v) 时，u 和 v 已经连通，则这条边形成了环，即是冗余边。

经典例题 3：账户合并

把所有属于同一人的账户合并（以邮箱为判断依据）。

List<List<String>> accountsMerge(List<List<String>> accounts) {
    Map<String, String> parent = new HashMap<>();  // email → email（并查集）
    Map<String, String> owner = new HashMap<>();   // email → name

    // 初始化：每个邮箱的父节点是自身
    for (List<String> acc : accounts) {
        String name = acc.get(0);
        for (int i = 1; i < acc.size(); i++) {
            parent.put(acc.get(i), acc.get(i));
            owner.put(acc.get(i), name);
        }
    }

    // find（路径压缩）
    // 为简洁用 lambda，实际建议写成方法
    java.util.function.Function<String, String> find = null;
    // ... 略（同上面的路径压缩写法）

    // 合并同一账户的所有邮箱
    for (List<String> acc : accounts) {
        String first = acc.get(1);
        for (int i = 2; i < acc.size(); i++) {
            // union(first, acc.get(i))
        }
    }

    // 整合结果：按根节点分组
    Map<String, TreeSet<String>> groups = new HashMap<>();
    // ...
    return new ArrayList<>();
}

并查集 vs. BFS/DFS

常见变体

• 带权并查集：rank 替换为权重，支持带权连通性（如食物链）
• 可撤销并查集（按秩合并，不压缩路径）：回滚上一次 union
• 连通分量数量：UnionFind.count 直接返回

小结

1. 路径压缩（find 时将整条路径接到根）可以显著降低树的高度
2. 按秩合并（union 时把小树接到大树）防止树退化为链
3. 两者合用，均摊时间 O(α(n)) ≈ O(1)
4. 适合解决：连通分量、动态连通性、检测环、集合合并问题