并查集

参考

OI Wiki 并查集, 这个网站是个宝库哦

引言

这个是 leetcode 上的一个求除法运算的题目, 我直接用的深度遍历做的, 然后看了下时间最短的那个, 用的是并查集, 我当时脑子懵了, 这都可以用并查集, 焯.

搜了下我的博客, 发现之前没有写并查集先关的文档, 这回补充一个算法介绍, 算法模板, 常见题目.

并查集的实现

struct UnionFind {
    vector <int> ancestor;

    UnionFind(int n) {
        ancestor.resize(n);
        for (int i = 0; i < n; ++i) {
            // 初始时, 每个元素都位于一个单独的集合, 表示为一棵只有根节点的树.
            // 方便起见, 我们将根节点的父亲设为自己.
            ancestor[i] = i;
        }
    }

    int find(int index) {
        // 我们需要沿着树向上移动, 直至找到根节点.
        return index == ancestor[index] ? index : find(ancestor[index]);
        // 查询过程中经过的每个元素都属于该集合, 我们可以将其直接连到根节点以加快后续查询.
        return index == ancestor[index] ? index : ancestor[index] = find(ancestor[index]);
    }

    void merge(int u, int v) {
        // 要合并两棵树, 我们只需要将一棵树的根节点连到另一棵树的根节点.
        ancestor[find(u)] = find(v);
    }
};

实现细节

查询: 我们需要沿着树向上移动, 直至找到根节点.
路径压缩: 查询过程中经过的每个元素都属于该集合, 我们可以将其直接连到根节点以加快后续查询.
合并: 要合并两棵树, 我们只需要将一棵树的根节点连到另一棵树的根节点.
启发式合并: 合并时, 选择哪棵树的根节点作为新树的根节点会影响未来操作的复杂度. 我们可以将节点较少或深度较小的树连到另一棵, 以免发生退化.
删除: 要删除一个叶子节点, 我们可以将其父亲设为自己. 为了保证要删除的元素都是叶子, 我们可以预先为每个节点制作副本, 并将其副本作为父亲.
移动: 与删除类似, 通过以副本作为父亲, 保证要移动的元素都是叶子.

时间复杂度

同时使用路径压缩和启发式合并之后, 并查集的每个操作平均时间仅为 $O(\alpha(n))$, 其中 $\alpha$ 为阿克曼函数的反函数, 其增长极其缓慢, 也就是说其单次操作的平均运行时间可以认为是一个很小的常数.

空间复杂度

显然为 $O(n)$.

带权并查集

我们还可以在并查集的边上定义某种权值, 以及这种权值在路径压缩时产生的运算, 从而解决更多的问题. 比如对于经典的「NOI2001」食物链, 我们可以在边权上维护模 3 意义下的加法群.

例题

UVA11987 Almost Union-Find

实现类似并查集的数据结构, 支持以下操作:

合并两个元素所属集合
移动单个元素
查询某个元素所属集合的大小及元素和

习题

其他应用

最小生成树算法中的 Kruskal 和最近公共祖先中的 Tarjan 算法是基于并查集的算法.

相关问题

求每个强联通分量的元素个数?

可以用一个数组记录根节点的元素个数, 每次合并就把被合并的元素个数加进来.

有多少个强联通分量?

方法 1: 判断元素根节点是自己的情况

if (parent[i] == i) {
    provinces++;
}

方法 2: 将最初的元素个数记为 $cnt$, 然后每次成功合并之后, 执行 $--cnt$.

public void union(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX == rootY) {
        return;
    }
    parent[rootX] = rootY;
    count--;
}

并查集是一种用于管理元素所属集合的数据结构, 实现为一个森林, 其中每棵树表示一个集合, 树中的节点表示对应集合中的元素.

顾名思义, 并查集支持两种操作: