并查集

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

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

举个奇怪的例子。

原理&代码实现+优化

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

我还没学会捏。