声明:与学校集训内容无关。
并查集是一种树形结构,基本的应用就是判断两个元素是否在同一个集合内,也可以将两个元素所在的集合合并。
举个奇怪的例子。
假设这里有一些P主,他们有不同的口味(派别),有摇滚,重金属,古典等等等。
现在我们假设有很多很多种口味,而我们设同一种口味的P主都是同事,会给出两个P主是同事关系,或询问两个P主是不是同事。
现在有一些P主,而我们假设初始时大家都是自成一派。
而我们将每个P主所在门派都选一个元老级的P主出来,i的直接元老是fa[i]。
所以刚开始元老都是自己:
for(int i=1;i<=n;++i){ fa[i]=i; }
这就是并查集的初始化了。
现在我们将八王子P和滚苹果P合并入同一个派别,当然,滚苹果是元老。
于是我们把fa[八王子P]=滚苹果P。
我们再将雄之助和八王子P合并到同一个派别,但是,雄之助的元老还是八王子P吗?显然不是,而是这个门派的元老,八王子P的元老,滚苹果P。
所以我们赋值时可以这么操作:
//把八王子和雄之助合并一下 x=fa[雄之助],y=fa[八王子]; fa[x]=y;
接着我们合并一下雄之助和chinozo。
但是雄之助的直接元老是八王子,但是真正的元老是滚苹果啊!
所以有了找真正的元老的函数find。
int find(int x){ return x==fa[x]?x:(find(fa[x])); }
那么合并也可以进化一下了。
void merge(int x,int y){ x=find(x),y=find(y); if(x!=y)fa[x]=y; return ; }
所以,我们就有了一个完整的P主管理并查集。
那我们如何优化?
学会了两个,一个路径压缩,一个按轶合并。
如果一起用的话路径压缩会影响轶的准确性,所以不要一起用。
实测,写luogu上面的模版,路径压缩比按轶合并快了13ms。
·路径压缩
当趋向于一条链的时候,就像我那个一样,八王子到滚苹果,雄之助到八王子,chinozo到雄之助,那如果我再做关于chinozo的操作,要走很长。
于是我们试图让路变得更短,从chinozo直接到滚苹果。
(所以我这个就直接变成菊花图了是吧)
int find(int x){ return x==fa[x]?x:(fa[x]=find(fa[x])); }
·按轶合并
如果两个帮派,一个有114层,另一个有514层,我们显然把114层的那个往514那个上面并。
所以我们用一个Rank[i]表示以i为根节点的门派或者子树的深度。
而两个Rank[x]和Rank[y]不相同的时候,合并后对Rank值无影响,但俩Rank相同时,其中一个Rank要++。
void merge(int x,int y){ x=find(x),y=find(y); if(x==y)return ; if(Rank[x]<=Rank[y])fa[x]=y; else fa[y]=x; if(Rank[x]==Rank[y])Rank[y]++; return ; }
于是就有了高级的优化。
1.判环
如P2661,想知道游戏会不会结束,看会不会有环,若有环,就会满足有一个i,使得i==find(t[i]),此时输出环的大小即可。
这就是一个带权并查集了。
2.种类并查集
我还没学会捏。