并查集 | nihility

数据结构

发布日期: 2022-06-19

更新日期: 2022-08-24

文章字数: 1.8k

阅读时长: 7 分

这篇文章我们不再讲解并查集的基础知识，主要讲解并查集的一些拓展用法，需要补一下基础知识的同学我推荐这一篇文章：并查集，另外这篇文章里讲到的按秩合并，也可以是把小的集合合并到大的集合上面，这样更容易代码实现，我们只需多维护一个集合的大小就可以了。另外按秩合并在不用可撤销并查集的地方我们基本上用不到，毕竟我们路径压缩后就很优秀了，而可撤销并查集不能使用路径压缩，我们为了保证效率就会使用按秩合并。另外提一嘴，使用路径压缩的并查集平均复杂度就是$O(n)$了。

带权并查集

我们在维护并查集的同时维护每个节点到当前它的父亲节点的距离，就能维护各个元素之间一些具有传递性的属性。感觉这一点干讲不知道怎么讲，我们就拿道题来看吧，第十三届篮球包（蓝桥杯）省赛CA组最后一题：

首先我们看到区间和肯定会想到并查集，我们用$s_{i}$表示$\sum_{j=1}^{i} A_{i}$，那么如果我们已知$\sum_{i=l}^{r} A_{i}$，就相当于知道了$s_{r}-s_{l-1}$，如果最终只是问我们答案能否确定，那肯定很简单，我们用并查集维护$s$的集合，我们只需要先合并它给我们的所有$r$和$l-1$，然后查询的时候看$l-1$和$r$是否在一个集合内即可。然后我们另外开一个数组$d$记录每个点$x$的父亲节点和它之间的差$s[p[x]]-s[x]$， $p[x]$表示$x$的父亲，至于$d$数组的初始化就很简单了，$d[i]=0$，因为刚开始$p[i]=i$，然后先看代码，我再具体讲解。

int l=read(),r=read();//read就是写的快读
LL sum=read();
l--;//前缀和为s[r]-s[l-1]
LL a=l,b=r;
l=find(l),r=find(r);//找到l-1，r的父亲p[l-1],p[r]
if(l!=r){
    p[l]=r;//合并集合，这里的l，r已经不是原来的l，r
    d[l]=sum+d[b]-d[a];//更新距离，为什么这么写，看下面的图应该就理解了
}

由于$find$函数调用的途中我们会改变节点的父亲，因此我们的$find$函数也需要改写。

int find(int x){
    if(p[x]!=x) {
        int root=find(p[x]);//先记录下找到的父亲
        d[x]+=d[p[x]];//x到新父亲的距离=x到旧父亲的距离+旧父亲到新父亲的距离
        p[x]=root;
    }
    return p[x];
}

//查询就比较简单了
int a=read(),b=read();
a--;
LL x=a,y=b;	
a=find(a),b=find(b);
if(a!=b) puts("UNKNOWN");
else cout<<d[x]-d[y]<<endl;//注意，这里是d[x]-d[y]而不是d[a]-d[b]，因为a，b已经变成它们的父亲了

到这里我们差不多了解了带权并查集，这里我们维护的是元素间的差，我们也可以维护其它类型的权值，大家可以自己找点题练习。

扩展域并查集

我们知道并查集能维护具有传递性的关系，但当我们遇到诸如“敌人的敌人是朋友”这类关系时，普通的并查集就没那么好用了，这时候我们的扩展域并查集就登场了。我们把并查集的规模扩大一倍，并划分为两个种类，在相同种类中合并两个元素表示他们是朋友，在不同种类中合并表达他们是敌人，这样一个人敌人的敌人就和他在同一个种类中，就维护了“敌人的敌人是朋友”的这种关系。

我们来道例题并写出代码加深一下理解。

我们还是用前缀和的思想，用$sum[i]$表示$s[1\sim i]$中1的个数，如果$l\sim r$中有偶数个$1$，我们易知$sum[l-1]$和$sum[r]$的奇偶性相同，奇数个则相反，而对于$sum[i]$，假设$sum[y]$与它奇偶性相反，那么与$sum[y]$奇偶性相反的数奇偶性与$sum[i]$相同，符合我们上面阐述的关系，因此这题我们可以用扩展域并查集来写。另外这题$N$的范围较大，需要离散化，我图个方便就直接写了，懂思路才是最重要的。

vector<int> p(2*n+2);//我们用0~n表示0~n的第一个种类，n+1~2*n+1表示0~n的第二个种类
int a=read(),b=read();
a--;
int pa1=find(a),pb1=find(b);
int pa2=find(a+n+1),pb2=find(b+n+1);
//是偶数个时，这二者奇偶性相同
if(pa1==pb2) break;//如果发现a，b奇偶性不同，说明矛盾
//否则无矛盾，正常合并
p[pa1]=pb1;
p[pa2]=pb2;
//奇数的情况也差不多，就不多写了

另外这题也能用带权并查集来写，我们维护的权值只有1和0，两点之间距离为0时说明奇偶性相同，为1时说明奇偶性不同，然后计算距离时对2取模即可。

最后留一道不错的练习题：食物链（带权并查集和扩展域并查集都能写）

可撤销并查集

顾名思义，可撤销并查集就是能撤销我们的合并操作的并查集，要撤销，我们就需要存储每一次修改的信息，然后就行回退，这时再使用路径压缩就会出现问题，如图。

因此我们使用按秩合并，此时每次find的时间复杂度为$O(log n)$，那我们怎么撤销呢？我们发现，我们每次合并只会改变一个集合的大小和一个点的父亲，我们把这些都记录下来，就能撤销了。

vector<pair<int,int>> his_p,his_sz;
int p[N],sz[N];//sz[i]表示以i为根的集合的大小，初始时sz[i]=1
//我们每进行一次合并his_p和his_sz的就会多一个元素，因此我们可以根据vector的大小来标识不同的历史版本
//不带路径压缩的find
int find(int x){
       while(p[x]!=x) x=p[x];
       return x;
   }
//合并部分代码
void merge(int a,int b){
       int pa=find(a),pb=find(b);
       if(pa==pb) return ;
       if(sz[pa]<sz[pb]) swap(pa,pb);
       his_sz.push_back({pa,sz[pa]});//pa的大小改变了
       sz[pa]=sz[pa]+sz[pb];//小的合并到大的上，即pb合并到pa上
       his_p.push_back({pb,p[pb]});//pb的父亲改变了
       p[pb]=pa;
   }
//撤销
void roll(int his){//回到vector大小为his的版本
       while(his_p.size()>his){
           p[his_p.back().first]=his_p.back().second;
           his_p.pop_back();
           sz[his_sz.back().first]=his_sz.back().second;
           his_sz.pop_back();
       }
   }