并查集和并查集

并查集的高级操作

维护并查集大小

siz[i]记录i节点所在集合的大小。

具体的做法是:

  • 在路径压缩回溯时,将当前节点的siz置为父节点的siz
  • 在合并两个集合的时候,要将合并之后集合的根节点的siz加上被合并的集合的siz,然后把被合并集合的siz置为合并后集合的siz
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int find(int i){
if(f[i]==i)return i;
int fi = f[i];
f[i]=find(f[i]);
siz[i]=siz[f[i]];
return f[i];
}
void update(int i,int j){
int fi=find(i),fj=find(j);
if(fi==fj)return;
f[fi]=fj;
siz[fj]+=siz[fi];
siz[fi]=siz[fj];
}

例题:

维护到根节点距离

思路与维护集合大小类似,具体来说:

  • 在路径压缩回溯时,将当前节点的dis加上父节点的dis
  • 在合并两个集合的时候,如果是连边到末尾,要将被合并集合根节点的dis置为合并后集合的根节点的原siz
  • 对于其他情况的dis更新方法视不同情况而定。

例题:

注:信息传递这道题由于"每人只会把信息告诉一个人"(出度全为1)的限定条件的存在,事实上可以用tarjan来求最小环(这也是我最开始想到的方法),但是这个方法必须要有这个限制条件的情况下才好用,反例请读者自行举出。

作者

李星烨

发布于

2020-11-24

更新于

2021-08-20

许可协议

CC BY-NC-SA 4.0

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×