关于并查集

技术分享 7个月前 (08-25) 0 999+

关注

P.S.:当前是挑战3个月冲击省一的第14天，距离CSP-J2开赛还有68天
这篇文章是由于昨天晚上做了一个有捆绑的01背包，需要使用并查集，我暂时使用dfs代替，遂决定，今天拿下
（毕竟数据结构这种东西什么猎奇算法都有可能用）

何为并查集

简单来说，就是需要对集合进行操作，包括：确认一个元素属于哪一个集合（或判断两个元素是否在同一个集合中）、合并两个集合；

而能做到以非常快的速度完成上面两个操作的数据结构就是————可以快速合并、查询的集合，简称 “并查集”

模版

下面是并查集的模版题：洛谷 P3367 【模板】并查集（难度：提高-）
我们借助这道题目进行对并查集的讲解

题目描述

如题，现在有一个并查集，你需要完成合并和查询操作。

## 输入格式
第一行包含两个整数 (N,M) ,表示共有 (N) 个元素和 (M) 个操作。
接下来 (M) 行，每行包含三个整数 (Z_i,X_i,Y_i) 。
当 (Z_i=1) 时，将 (X_i) 与 (Y_i) 所在的集合合并。
当 (Z_i=2) 时，输出 (X_i) 与 (Y_i) 是否在同一集合内，是的输出
`Y` ；否则输出 `N` 。

## 输出格式
对于每一个 (Z_i=2) 的操作，都有一行输出，每行包含一个大写字母，为 `Y` 或者 `N` 。

## 数据范围：
对于 (100%) 的数据，(1le Nle 2times 10^5)，(1le Mle 10^6)，(1 le X_i, Y_i le N)，(Z_i in { 1, 2 })。

WriteUp

并查集的时间复杂度为 (Theta(alpha(n))) ，将其换为大O标记，就是平均复杂度；
这里的 (alpha(n)) 为反阿克曼函数，增长极其缓慢，可以认为一般小于4，也就是常数级；

这里先讲讲并查集是如何做到快速操作的：
对于每个集合，并查集都选取一个代表元素，简称代表元，对于查询两个元素是否在同一个集合中的操作，只需要看看这两个元素所在集合的代表元是否一样即可；

那么如何找代表元呢：
当每个元素各自属于一个集合时，他们的代表元为自己，记为 (w_x) ；
若一个集合中有不止1个元素，证明这个集合是由另外的集合合并过来的，因此现在的问题转换成了：合并时如何修改代表元；

每次当我们合并两个集合时（注意：也包括上面单一元素的情况），我们只需要将一个集合中所有元素的代表元设为另一个集合的代表元即可，现在请读者思考一下这样做的时间复杂度是多少；
显然，是线性的，即 (O(n)) 级别，但是我们注意到，查询操作是 (O(1)) 的，这提示我们，通过提高查询操作的时间，有可能能够降低合并操作的时间；

这里补充一点树的知识：众所周知，树的一枝上会有分叉，分叉之后可能会有叶，也可能再分叉，我们如果将分叉点和叶都抽象成点，那么紧跟着一个分叉点的叶和这个分叉点就有“父子关系”，称分叉点为叶节点的直接父亲（直接前驱），叶节点称为子节点，分叉点称为父节点；

还记得何为 (w_x) 吗，我们定义为元素 (x) 所在集合的代表元；
我们修改一下： (w_x) 为元素 (x) 的直接父亲，特别的，当这个元素为某个集合的代表元时，它的直接父亲为它自己；

每次合并时，我们先令一个集合为父，另一个为子，找到父集的代表元，将子集的代表元的直接父亲设为父集代表元；
打个比方：如果小A是B的员工，现在B所在部门要合并到C的部门，那么B的上司为C，C自然也是A的一个领导了；
这里A、B的所在集合的代表元就是B，而与C合并时直接将B的父亲设为C，自然A也属于C了；

下一个问题是：如何寻找一个集合的代表元：

我们定义： (find(x)) 为寻找一个元素所在集合的代表元的函数，显然，当 (w_x = x) 时，就找到了代表元，因为根据定义，只有代表元的父节点是其本身；
现在我们还是回到刚才的比喻：小A现在想找到管自己的最大的一个人，它就先找了B，问了B同样的问题，B又去找了自己的顶头上司C，C发现自己就是最大的，于是告诉B，B告诉A，小A就知道了；
所以当 (w_x not= x) 时，我们就需要对父节点继续进行 (find(x)) 这个操作，直到找到了代表元；

如果读者比较细心，就会发现，目前的复杂度仍然不是常数级，在每次合并时，都需要进行一次 (find(x)) ，而 (find(x)) 的复杂度是跟深度有关的（比如小A有100个上司，那么查找自己的总经理的询问次数就是100次），是 (O(n)) 线性级；

所以，目前的并查集仍然不是完全体，我们需要进一步优化；
如果我们在小A得到了自己的总经理是C这个结果之后，直接让小A的父节点为C，那么下次小A的下级（如果有的话）询问自己的总经理是谁是，就能跳过B这一步，直接从小A这里得到了答案；
更一般的，我们如果小A到C之间有100个人，当小A询问完之后，让这里每一个人的父节点都是C，那么下次任何一个人询问的成本都将是1次，常数级，这就是我们想要的；
也就是大名鼎鼎的————“并查集之路径压缩”

具体的讲，就是每次执行 (find(x)) 这个操作时，我们把所有节点的父节点都设为代表元，这样下一次的合并操作就是 (O(1)) 的；
当然，第一次执行 (find(x)) 这个操作时没有这种优化效果；

我们回到最开始的问题：
我们需要并查集能够在常数时间内完成：1.合并两个元素所在集合 2.判断两个元素是否在同一个集合中；
现在显然，1我们已经通过代表元和路径压缩做到了，那么2呢；（这里如果读者反应过来了，可以略过）
对于2，我们只需要判断 (find(x)) 是否等于 (find(y)) ，就OK了；
而 (find(x)) 在路径压缩下是近似 (O(1)) 的，所以，全部的目标达成；

下面给出C++的代码：

#include<iostream> using namespace std; const int MAXN = 2e5+7; int fa[MAXN]; int n,m; int op,u,v; int find(int x){     if(fa[x]==x) return x; //找到了代表元     fa[x] = find(fa[x]);   //询问父节点，并将代表元设为询问节点的父节点     return fa[x]; } void union_set(int x,int y){     int p = find(x),q = find(y);     fa[q] = p;    //将y所在集合的代表元的父节点设为x所在集合的代表元 } bool if_same(int x,int y){     return find(x)==find(y); } /*   初始化函数，参数为元素数量； */ void init(int x) {     for (int i=1;i<=x;i++) {         fa[i] = i;     } } int main() {     cin>>n>>m;     init(n);     for(int i=0;i<m;i++) {         cin>>op>>u>>v;         if (op==1) union_set(u,v);         else {             bool tmp = if_same(u,v);             if (tmp) {                 cout<<"Y"<<endl;             }else {                 cout<<"N"<<endl;             }         }     }     return 0; }

一些补充：

1.反阿克曼函数的增长真的非常非常慢，在操作数 (N le 10^{18}) 的情况下都小于4
2.平均复杂度的说法是不严谨的，应该是均摊复杂度接近常数级
3.这里没有提到“按秩合并”的方法，在一般情况下，路径压缩的算法已经很优，再使用按秩合并意义不大，不过如果是OI竞赛，建议带上，这里受限于篇幅，暂不介绍

不过提一嘴：所谓的秩，就是树的高度，当合并两个集合时，将树矮的集合并到树高的集比较好，具体原因可以想想有100个上司的小A
实现很简单，增加一个辅助数组即可；

4.find函数在递归深度比较大时可能爆栈，可以改成循环实现，也很简单；