Java教程

并查集

本文主要是介绍并查集,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

声明:与学校集训内容无关。

并查集是一种树形结构,基本的应用就是判断两个元素是否在同一个集合内,也可以将两个元素所在的集合合并。

举个奇怪的例子。

原理&代码实现+优化

假设这里有一些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.种类并查集

我还没学会捏。

这篇关于并查集的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!