跳到主要内容

并查集

并查集（Union-Find），也称为不相交集合数据结构（Disjoint-Set），主要用于处理一些 不相交集合的合并及查询。

核心操作​

并查集提供两个核心操作：

  1. Find：确定某个元素属于哪一子集。即判断两个特定元素是否属于同一子集。
  2. Union：将两个子集归并成一个集合。

优化策略​

1. 路径压缩 (Path Compression)​

在执行 find 操作时，将节点的父指针指向其祖先，使得以后再查询该节点及其子节点时速度更快。目标是使树变得“扁平”。

2. 按秩合并 (Union by Rank/Size)​

在执行 union 操作时，总是将高度（秩）较小的树根连接到高度较大的树根下，从而控制树的高度。

实现代码​

public class UnionFind {
    private int[] parent;
    private int count; // 集合数量

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

    // Find with Path Compression - O(α(n)) 接近 O(1)
    public int find(int p) {
        if (parent[p] != p) {
            parent[p] = find(parent[p]); // 路径压缩
        }
        return parent[p];
    }

    // Union - O(α(n))
    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ) return;
        parent[rootP] = rootQ; // 简单合并
        count--;
    }

    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }

    public int count() {
        return count;
    }
}

典型应用​

  1. 图的连通性：统计连通分量的数量。
  2. Kruskal 算法：检测边是否成环，构建最小生成树。
  3. 社交网络动态连接检测。

练习​

  1. LeetCode 547：省份数量
  2. LeetCode 200：岛屿数量 (可以使用 BFS/DFS, 也可以用并查集)
  3. LeetCode 684：冗余连接
  4. LeetCode 990：等式方程的可满足性