跳到主要内容

并查集

问题​

Java 中并查集（Union-Find）的原理和常见题目有哪些？

答案​

并查集用于处理动态连通性问题：合并集合、查询两元素是否属于同一集合。

并查集模板​

路径压缩 + 按秩合并
class UnionFind {
    int[] parent;
    int[] rank;
    int count;  // 连通分量数
    
    UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        count = n;
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    
    // 查找根节点（路径压缩）
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    
    // 合并两个集合（按秩合并）
    void union(int x, int y) {
        int rootX = find(x), rootY = find(y);
        if (rootX == rootY) return;
        if (rank[rootX] < rank[rootY]) { int tmp = rootX; rootX = rootY; rootY = tmp; }
        parent[rootY] = rootX;
        if (rank[rootX] == rank[rootY]) rank[rootX]++;
        count--;
    }
    
    boolean connected(int x, int y) { return find(x) == find(y); }
}
复杂度

路径压缩 + 按秩合并后，find 和 union 的均摊时间复杂度为 O(α(n))O(\alpha(n))，其中 α\alpha 是阿克曼函数的反函数，实际可视为 O(1)O(1)。

朋友圈 / 省份数量（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.count;
}

冗余连接（LeetCode 684）​

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

岛屿数量（并查集解法）​

二维转一维，合并相邻陆地
public int numIslands(char[][] grid) {
    int m = grid.length, n = grid[0].length;
    UnionFind uf = new UnionFind(m * n);
    int water = 0;
    int[][] dirs = {{1, 0}, {0, 1}};
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '0') { water++; continue; }
            for (int[] d : dirs) {
                int ni = i + d[0], nj = j + d[1];
                if (ni < m && nj < n && grid[ni][nj] == '1') {
                    uf.union(i * n + j, ni * n + nj);
                }
            }
        }
    }
    return uf.count - water;
}

常见面试问题​

Q1: 并查集 vs BFS/DFS 求连通分量？​

答案：

对比并查集BFS/DFS
动态加边✅ 支持❌ 需重新遍历
时间复杂度近 O(1)O(1) 每次操作O(V+E)O(V + E) 全量遍历
适用场景动态连通性、在线查询静态图遍历

Q2: 路径压缩有什么作用？​

答案：

find 时直接把节点挂到根节点下，使树高度趋近于 1，后续查找几乎 O(1)O(1)。

相关链接​