浅谈并查集优化

并查集是一种可以动态维护若干个不重叠的集合，并资瓷合并与查询的数据结构（~~这么水不配叫数据结构~~） （接下来的内容过于菜，请大佬出门左转） 并查集最基本的操作是查询与合并，为了提高效率，我们常用的我们引入了路径压缩与按秩合并两种思想 ## 路径压缩（最常用）： ``` int get(int x){ if(x==f[x])return x; f[x]=get(f[x]); return f[x]; } void unionn(int x,int y){ int u=get(x),v=get(y); if(u!=v)f[u]=v; } ``` 给大家放张图理解下路径压缩的工作原理：  路径压缩的效率很高，可以做到$log$级别，可以防止树的形态变为一条链，在一般并查集中应用很广泛，一旦使用路径压缩，原有的父子关系就会被破坏，从而直接建立与祖先的父子关系，可以高效地维护集合之间的从属关系，但是对于每个节点之间的直接关系是不能维护的 路径压缩这里不再过多解释~~毕竟这么简单~~，我们来简述一下按秩合并，按秩合并分为按大小合并和按深度合并两种，按大小合并是很容易想到也很容易维护的，而按深度合并则是要将整个体系的从属关系抽象成一棵树，每次将深度小的合并到深度较大的树上，这样的话不论深度小的那棵树有多深，合并后的树的深度都不会大于一开始时的较大深度。 ## 按秩合并： ``` int get(int x){ while(f[x])x=f[x]; return x; } void unionn(int x,int y){//按大小合并 int u=get(x),v=get(y); if(u!=v){ if(size[u]<size[v]){ f[u]=v; size[v]+=size[u]; //按大小合并每次要更新大小 } else{ f[v]=u; size[u]+=size[v]; } } } ``` ``` void unionn(int x,int y){//按深度合并 int u=get(x),v=get(y); if(u!=v){ if(high[u]<hige[v])f[u]=v; else { f[v]=u; if(high[u]==high[v])high[u]++; //按深度合并只有在两树高度相等的时候更新 } } } ``` 而按秩合并与树的形态关系很密切，虽然不能像路径压缩一样快速处理两点是否有从属关系，它能很好地维护树的形态与父子关系，可以维护出每个子节点的直接父亲，这是路径压缩所不能做到的，由此来看，两种优化方式可以说是各有千秋。 这两种方法多数情况下是可以一起用的，既用路径压缩，又用按秩合并当然可以提高效率，复杂度增长速度为为阿克曼函数的反函数，不过只用路径压缩达到的效果($log$)在多数情况下也可以与之媲美，当然啦，依照个人习惯而定，愿意两个都用的当然可以，不过有时候按秩合并是不能与路径压缩一起使用的。仔细想一想我们刚才说到的性质，如果题目需要维护明确的父子关系而用到了按秩合并的话，是不能用路径压缩的，像上边所说，一旦用了路径压缩，会破坏树的形态，原来的节点会直接压缩到祖先上，这样一来我们调用的时候父子关系发生了改变，造成了算法的错误。 那么基础就讲到这里，下面看一下经典的扩展域和边带权问题 ## 扩展域 首先让我们从一道题目入手： 放一道老题 [食物链](https://www.luogu.org/problemnew/show/P2024) 因为题目告诉我们每三种动物构成一条食物链，我们可以将每种动物分成三部分，即同类$self$、捕食$eat$、天敌$enemy$，，那我们不妨将并查集数组开大三倍，作为并查集的扩展域。 即本身对应第一倍，猎物对应第二倍，天敌对应第三倍 嗯，举个栗子 如果是同类，就合并他们本身，他们的敌人,他们的猎物 ``` unionn(x,y); unionn(x+n,y+n) unionn(x+2*n,y+2*n); //(n为一倍大小） ``` 如果$x$吃$y$，说明$x$是$y$的天敌，那$x$的天敌就是$y$捕食的物种，也就是$x$吃$y$，$y$吃$z$，$z$吃$x$ ``` unionn(x+n,y); unionn(x,y+2*n); unionn(x+2*n,y+n); ``` 每次先判断是不是假话，也就是看一下是否已经被合并过，并且之前合并的关系与当前关系是否冲突，然后就可以按照题目所给出的关系进行合并啦~ 在做这道题之前不妨先做一下这道题 [团伙](https://www.luogu.org/problemnew/show/P1892) 食物链是这道题运用的反集思想的扩展，(食物链用的是三倍空间，团伙用的是二倍)做完这道题再来做食物链可能更好理解~~（双倍经验）~~ ## 边带权 依然从一道老掉牙的题目开始 [银河英雄传说](https://www.luogu.org/problemnew/show/P1196) 因为在并查集中存在着父子关系，所以也就有了树的形态，整个并查集数组就可以看成由若干棵树组成的森林，对于每个点维护一个数组d[]保存节点x到父亲节点fa[]之间的边权。 稍微放一下伪代码（逃： ``` int get(int x){ if(x==fa[x])return x; int f=fa[x]; fa[x]=get(fa[x]); dis[x]+=dis[f];//与祖先的距离 size[x]=size[fa[x]];//这个集合的大小 return fa[x]; } ``` 因为每次路径压缩后这个点都会直接指向祖先，那么，不妨直接利用路径压缩来更新d[]（就是将维护数组的过程放在路径压缩中），这样，对于每一次询问祖先都能更新对应的边权，在最后调用结果的时候重新更新一遍就能保证其正确性。 理解了的话就再来一道$QwQ$ [叠积木](https://www.luogu.org/problemnew/show/P2342)（二倍经验） 代码什么的我相信你会写 ~~（不放代码就跑真开心~）~~ ## 并查集求环 由于并查集能维护父子关系，所以我们也可以将它运用到图论中，比如这道题[信息传递](https://www.luogu.org/problemnew/show/P2661)，对于一个环，势必有一个点的父亲是他的子孙节点，（画个图很好理解的），如果发现将要成为自己父亲的节点是自己几代之后的子孙，这就说明有环出现了，用边带权并查集维护儿子是哪一代就可以求出环的大小，就可以进一步求最大环、最小环之类的东西啦，当然这只是并查集思路，这类题目还有另一种解法——$tarjan$（强烈安利）~~就是裸的缩点~~。 好的，如果理解了就来看下这道加强版[在农场万圣节](https://www.luogu.org/problemnew/show/P2921) ~~又不放代码啦啦啦~~ 特意去学了下可持久化并查集，发现她和并查集并没有很大的关系，所以这里不介绍啦（并不是偷懒） 以上，希望我的讲解能对大家有帮助 qwq 最后希望大家 noip2018 rp++! ~~估计发出来的时候我已经退役了~~ 猛然发现之前自己做的图片挂了，感谢好心的管理大大帮我配图$QAQ$~~虽然做之前那个图片我很用心的,好可惜嘤嘤嘤~~（怎么感觉管理大大的图片风格很诡异2333