跳到主要内容

并查集

并查集（Union-Find），也称为不相交集合数据结构（Disjoint-Set Union, DSU），是一种用于管理元素分组的数据结构。它主要用于处理不相交集合的合并及查询问题，支持高效地判断两个元素是否属于同一集合，以及合并两个集合。

核心概念​

什么是并查集？​

假设有 n 个元素，初始时每个元素自成一个集合。并查集支持两种操作：

  • Union（合并）：将两个元素所在的集合合并为一个集合
  • Find（查找）：查找某个元素属于哪个集合，通常返回该集合的代表元素

这两个操作的组合可以解决很多"动态连通性"问题。

现实应用场景​

  • 社交网络：判断两个人是否在同一个朋友圈
  • 图像处理：统计连通区域的数量
  • 网络连接：判断网络中两点是否连通
  • 最小生成树：Kruskal 算法中判断边的两个端点是否已连通

基本原理​

集合的树形表示​

并查集使用森林来表示多个集合：每个集合用一棵树表示，树的根节点就是该集合的代表元素（也称为"首领"或"老大"）。

初始状态（5个元素各自为集合）：
元素:  0   1   2   3   4
父节点: 0   1   2   3   4   (每个元素指向自己)

合并(0, 1) 和 合并(2, 3) 后：
元素:  0   1   2   3   4
父节点: 0   0   2   2   4   (1指向0，3指向2)

再合并(0, 2) 后：
元素:  0   1   2   3   4
父节点: 0   0   0   2   4   (集合{0,1,2,3}的根是0)

基本操作​

Find 操作：从元素出发，沿着父指针一直向上找，直到根节点。根节点的特征是父指针指向自己。

Union 操作：先找到两个元素的根节点，如果根节点不同，就把一个根节点指向另一个根节点。

基础实现​

public class UnionFind {
    private int[] parent;  // parent[i] 表示元素 i 的父节点
    private int count;     // 集合的数量
    
    public UnionFind(int n) {
        parent = new int[n];
        count = n;
        // 初始化：每个元素的父节点是自己
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    
    // 查找元素所属集合的根节点
    public int find(int x) {
        while (parent[x] != x) {
            x = parent[x];
        }
        return x;
    }
    
    // 合并两个元素所在的集合
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        
        if (rootX != rootY) {
            parent[rootX] = rootY;  // 将一个根指向另一个根
            count--;
        }
    }
    
    // 判断两个元素是否在同一集合
    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }
    
    // 返回集合数量
    public int count() {
        return count;
    }
}

基础实现的问题​

基础实现的效率不高，因为 find 操作的时间复杂度取决于树的高度。在最坏情况下，树可能退化成链表，高度为 O(n)O(n)，导致 nn 次 union 操作的时间复杂度为 O(n2)O(n^2)。

优化策略​

路径压缩（Path Compression）​

核心思想：在执行 find 操作时，让路径上的所有节点直接指向根节点，从而"压扁"树。

原树结构：           路径压缩后：
    0                   0
   / \                 /|\
  1   2      -->      1 2 3
 /
3

实现方式：

// 递归实现（更简洁）
public int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);  // 路径压缩
    }
    return parent[x];
}

// 迭代实现（避免栈溢出）
public int find(int x) {
    int root = x;
    // 先找到根节点
    while (parent[root] != root) {
        root = parent[root];
    }
    // 路径压缩：将路径上所有节点直接指向根
    while (parent[x] != root) {
        int next = parent[x];
        parent[x] = root;
        x = next;
    }
    return root;
}

路径压缩后，树的深度大大降低，find 操作的平摊时间复杂度接近 O(1)O(1)。

按秩合并（Union by Rank）​

核心思想：在合并两个集合时，将较矮的树挂到较高的树下，避免树的高度增加。

秩（Rank）的定义：树的高度上界。初始时每个节点的秩为 0。

public 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;
            rank[i] = 0;
        }
    }
    
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        
        if (rootX != rootY) {
            // 按秩合并：将矮树挂到高树下
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                // 高度相等，任意挂，但需要增加秩
                parent[rootY] = rootX;
                rank[rootX]++;
            }
            count--;
        }
    }
    
    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }
    
    public int count() {
        return count;
    }
}

按大小合并（Union by Size）​

另一种策略是按集合大小合并：将较小的集合挂到较大的集合下。

public class UnionFind {
    private int[] parent;
    private int[] size;   // size[i] 表示以 i 为根的集合大小
    private int count;
    
    public UnionFind(int n) {
        parent = new int[n];
        size = new int[n];
        count = n;
        
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }
    
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        
        if (rootX != rootY) {
            // 按大小合并：小集合挂到大集合下
            if (size[rootX] < size[rootY]) {
                parent[rootX] = rootY;
                size[rootY] += size[rootX];
            } else {
                parent[rootY] = rootX;
                size[rootX] += size[rootY];
            }
            count--;
        }
    }
    
    // 获取元素所在集合的大小
    public int getSize(int x) {
        return size[find(x)];
    }
    
    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }
    
    public int count() {
        return count;
    }
}

时间复杂度分析​

各版本对比​

实现方式Find 时间复杂度Union 时间复杂度
基础实现O(n)O(n)O(n)O(n)
只用路径压缩O(log⁡n)O(\log n) 平摊O(log⁡n)O(\log n) 平摊
只用按秩合并O(log⁡n)O(\log n)O(log⁡n)O(\log n)
两者结合O(α(n))O(\alpha(n))O(α(n))O(\alpha(n))

阿克曼函数​

α(n)\alpha(n) 是阿克曼函数的反函数，增长极其缓慢。对于任何实际应用中的 nn（即使 n=10600n = 10^{600}），α(n)≤4\alpha(n) \leq 4。因此，使用路径压缩和按秩合并的并查集操作可以认为是近乎常数时间的。

数学表达： α(n)=min⁡{k:Ak(1)≥n}\alpha(n) = \min\{k : A_k(1) \geq n\}

其中 AkA_k 是阿克曼函数。

完整实现​

以下是生产级别的并查集实现，包含路径压缩和按大小合并：

public class UnionFind {
    private int[] parent;
    private int[] size;
    private int count;
    
    /**
     * 初始化并查集
     * @param n 元素数量
     */
    public UnionFind(int n) {
        if (n <= 0) {
            throw new IllegalArgumentException("元素数量必须为正数");
        }
        
        parent = new int[n];
        size = new int[n];
        count = n;
        
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }
    
    /**
     * 查找元素 x 所属集合的根节点（带路径压缩）
     * @param x 待查找的元素
     * @return 根节点
     */
    public int find(int x) {
        if (x < 0 || x >= parent.length) {
            throw new IndexOutOfBoundsException("元素索引越界");
        }
        
        // 路径压缩：递归查找并更新父节点
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    /**
     * 合并元素 x 和 y 所在的集合
     * @param x 第一个元素
     * @param y 第二个元素
     */
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        
        // 已经在同一集合
        if (rootX == rootY) {
            return;
        }
        
        // 按大小合并：小集合挂到大集合下
        if (size[rootX] < size[rootY]) {
            parent[rootX] = rootY;
            size[rootY] += size[rootX];
        } else {
            parent[rootY] = rootX;
            size[rootX] += size[rootY];
        }
        
        count--;
    }
    
    /**
     * 判断元素 x 和 y 是否在同一集合
     */
    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }
    
    /**
     * 获取元素 x 所在集合的大小
     */
    public int getSetSize(int x) {
        return size[find(x)];
    }
    
    /**
     * 获取当前集合数量
     */
    public int count() {
        return count;
    }
    
    /**
     * 重置并查集（每个元素独立成集合）
     */
    public void reset() {
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
            size[i] = 1;
        }
        count = parent.length;
    }
}

典型应用​

1. 统计连通分量数量​

public int countComponents(int n, int[][] edges) {
    UnionFind uf = new UnionFind(n);
    
    for (int[] edge : edges) {
        uf.union(edge[0], edge[1]);
    }
    
    return uf.count();
}

2. 判断图是否有环​

对于无向图，如果添加边时两个顶点已经在同一集合，则存在环。

public boolean hasCycle(int n, int[][] edges) {
    UnionFind uf = new UnionFind(n);
    
    for (int[] edge : edges) {
        int u = edge[0], v = edge[1];
        
        if (uf.connected(u, v)) {
            // u 和 v 已经连通，添加这条边会形成环
            return true;
        }
        
        uf.union(u, v);
    }
    
    return false;
}

3. Kruskal 最小生成树算法​

public int minimumSpanningTree(int n, int[][] edges) {
    // 按权重排序边
    Arrays.sort(edges, (a, b) -> a[2] - b[2]);
    
    UnionFind uf = new UnionFind(n);
    int totalWeight = 0;
    int edgeCount = 0;
    
    for (int[] edge : edges) {
        int u = edge[0], v = edge[1], weight = edge[2];
        
        // 如果 u 和 v 不连通，选择这条边
        if (!uf.connected(u, v)) {
            uf.union(u, v);
            totalWeight += weight;
            edgeCount++;
            
            // 已经选了 n-1 条边，完成
            if (edgeCount == n - 1) {
                break;
            }
        }
    }
    
    // 检查是否所有顶点都连通
    return edgeCount == n - 1 ? totalWeight : -1;
}

4. 岛屿数量（LeetCode 200）​

将岛屿问题转化为连通分量问题：

public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) {
        return 0;
    }
    
    int rows = grid.length;
    int cols = grid[0].length;
    UnionFind uf = new UnionFind(rows * cols);
    
    int waterCount = 0;
    
    // 遍历网格，合并相邻的陆地
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (grid[i][j] == '0') {
                waterCount++;
                continue;
            }
            
            int index = i * cols + j;
            
            // 只需检查右边和下边（避免重复）
            if (j + 1 < cols && grid[i][j + 1] == '1') {
                uf.union(index, i * cols + (j + 1));
            }
            if (i + 1 < rows && grid[i + 1][j] == '1') {
                uf.union(index, (i + 1) * cols + j);
            }
        }
    }
    
    // 岛屿数 = 总格子数 - 水格数 - 实际合并次数
    return uf.count() - waterCount;
}

5. 省份数量（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();
}

6. 冗余连接（LeetCode 684）​

找出一棵树中最后添加的边：

public int[] findRedundantConnection(int[][] edges) {
    int n = edges.length;
    UnionFind uf = new UnionFind(n + 1);
    
    for (int[] edge : edges) {
        int u = edge[0], v = edge[1];
        
        if (uf.connected(u, v)) {
            // u 和 v 已经连通，这条边是冗余的
            return edge;
        }
        
        uf.union(u, v);
    }
    
    return new int[0];
}

7. 等式方程的可满足性（LeetCode 990）​

处理相等和不等关系：

public boolean equationsPossible(String[] equations) {
    UnionFind uf = new UnionFind(26);  // 26 个字母
    
    // 第一遍：处理所有相等关系
    for (String eq : equations) {
        if (eq.charAt(1) == '=') {
            int a = eq.charAt(0) - 'a';
            int b = eq.charAt(3) - 'a';
            uf.union(a, b);
        }
    }
    
    // 第二遍：检查不等关系是否冲突
    for (String eq : equations) {
        if (eq.charAt(1) == '!') {
            int a = eq.charAt(0) - 'a';
            int b = eq.charAt(3) - 'a';
            if (uf.connected(a, b)) {
                return false;  // 冲突
            }
        }
    }
    
    return true;
}

进阶应用​

动态连通性​

并查集特别适合处理动态添加边、查询连通性的场景。相比 DFS/BFS 每次查询需要 O(V+E)O(V+E)，并查集每次查询只需 O(α(n))O(\alpha(n))。

离线查询​

当所有查询事先已知时，可以按特定顺序处理查询，利用并查集高效解决。例如：

  • 最近公共祖先（LCA）的 Tarjan 算法
  • 区间最小值查询的离线算法

滚动并查集​

在处理二维网格或矩阵时，可以按行滚动处理，节省空间：

// 处理图像连通区域时，只需保存上一行的信息
public int[] processRowByRow(char[][] grid) {
    int cols = grid[0].length;
    UnionFind uf = new UnionFind(2 * cols);  // 只存两行
    
    // ... 滚动处理逻辑
    return null; // 简化示例
}

小结​

并查集是一种简单而强大的数据结构：

核心要点：

  • 用森林表示多个集合
  • find 查找根节点，union 合并集合
  • 路径压缩 + 按秩/大小合并 = 近乎常数时间

适用场景：

  • 动态连通性问题
  • 最小生成树算法
  • 判断图的连通性、是否有环
  • 集合合并与查询

使用建议：

  • 需要频繁合并和查询 → 并查集
  • 需要删除操作 → 不适合并查集
  • 需要获取连通分量具体内容 → 配合其他数据结构

练习​

基础：

  1. LeetCode 547：省份数量
  2. LeetCode 200：岛屿数量
  3. LeetCode 990：等式方程的可满足性

进阶： 4. LeetCode 684：冗余连接 5. LeetCode 685：冗余连接 II 6. LeetCode 1319：连通网络的操作次数 7. LeetCode 721：账户合并 8. LeetCode 765：情侣牵手

挑战： 9. LeetCode 803：打砖块 10. LeetCode 952：按公因数计算最大组件大小 11. LeetCode 1202：交换字符串中的元素 12. LeetCode 1697：检查边长度限制的路径是否存在