并查集

HeChuangJun约 1078 字大约 4 分钟

并查集理论基础

并查集主要有两个功能：将两个元素添加到一个集合中。判断两个元素在不在同一个集合
思想：用一个一维数组表示三个元素A，B，C （分别是数字）在同一个集合，即father[A]=B，father[B]=C 表示A与B与C连通了（有向连通图）。但无法也无需知道B连通A，类似树的结构，把root当成分类的标准，当root都相等的时候，说明在同一个集合
怎么判断元素联通/元素在同一个集合，只需要递归求得元素的根是否是同一个，
怎么表示C也在同一个元素集合里呢？只需 father[C] = C，即C的根也为C，所以father数组初始化的时候要 father[i] = i，默认自己指向自己。
路径压缩：为了避免在多叉树情况下寻根递归次数过多，将非根节点的所有节点直接指向根节点。只需要在递归的过程中，让 father[u] 接住递归函数 find(father[u]) 的返回结果。

并查集的模板

public class UnionFind {
    private int[] father;
    private int n;

    // 构造函数初始化并查集
    public UnionFind(int n) {
        this.n = n;
        father = new int[n];
        init();
    }

    // 并查集初始化
    private void init() {
        for (int i = 0; i < n; i++) {
            father[i] = i;
        }
    }

    // 并查集里寻根的过程
    public int find(int u) {
        if (u != parent[u]) {
            parent[u] = find(parent[u]); // 路径压缩，将当前节点指向根节点
        }
        return parent[u];
    }

    // 判断 u 和 v 是否属于同一个集合
    public boolean isSame(int u, int v) {
        return find(u) == find(v);
    }

    // 将 v -> u 这条边加入并查集
    public void join(int u, int v) {
        u = find(u); // 寻找 u 的根
        v = find(v); // 寻找 v 的根
        if (u != v) { // 如果不在同一个根，将 v 的根设置为u
            father[v] = u;
        }
    }

    // 测试方法
    public static void main(String[] args) {
        int n = 1005; // 假设有 1005 个节点
        UnionFind uf = new UnionFind(n);

        // 示例操作
        uf.join(1, 2);
        uf.join(2, 3);
        System.out.println(uf.isSame(1, 3)); // 输出 true
        System.out.println(uf.isSame(1, 4)); // 输出 false

        uf.join(3, 4);
        System.out.println(uf.isSame(1, 4)); // 输出 true
    }
}

通过模板，我们可以知道，并查集主要有三个功能。

寻找根节点，函数：find(int u)，也就是判断这个节点的祖先节点是哪个
将两个节点接入到同一个集合，函数：join(int u, int v)，将两个节点连在同一个根节点上
判断两个节点是否在同一个集合，函数：isSame(int u, int v)，就是判断两个节点是不是同一个根节点

常见误区
模板中的 join 函数里的这段代码：

u = find(u); // 寻找u的根
v = find(v); // 寻找v的根
if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回

与 isSame 函数的实现是不是重复了？如果抽象一下呢，代码如下：

// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}

// 将v->u 这条边加入并查集
void join(int u, int v) {
    if (isSame(u, v)) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
    father[v] = u;
}

空间复杂度： O(n) ，申请一个father数组。
时间复杂度在O(logn)与O(1)之间，且随着查询或者合并操作的增加，时间复杂度会越来越趋于O(1)。
在第一次查询的时候，相当于是n叉树上从叶子节点到根节点的查询过程，时间复杂度是logn，
路径压缩后，后面的查询操作都是O(1)，而 join 函数和 isSame函数里涉及的查询操作也是一样的过程。

使用场景

Kruskal 最小生成树算法
网格渗透
网络连通性
树中的东方共同祖先
图像处理

复杂度

Construction O(n)
Union α(n)
Find α(n)
Get component size α(n)
Check if connected α(n)
Count components O(1)
α摊销固定时间