并查集（路径压缩、按秩合并、按大小合并）

并查集

简单介绍：

并查集是一种树形的数据结构，可以用它处理一些不交集合并、查询以及连通块等问题。通常包含以下两个操作：

find：查询两个元素是否为同一集合

merge：将两个集合合并为一个集合

初始化：

我们可以将同一集合的元素存到一个类似于树的结构，用一个数组fa[N]来存储，我们将其初始化为i：

for(int i=1;i<=n;i++)
{fa[i]=i;
}

当有别的同一集合元素出现时，我们可以改变其fa[i]的值,为什么初始化为i？

因为这样可以用是否fa[i]=i来判断该节点是否为祖宗节点，我们在看完查找或许会更清晰明白

如何查找？

1. 我们每次同一集合的会存储在同一树的结构，因此当我们判断两个元素的祖宗节点是否相同即可
2. 此时便用到上文提到的判断是否为祖宗结点的方法
3. 如果判断a，b元素是否为同一集合元素，先对a进行处理，如果a为祖宗节点（fa[i]=i),则将a值返回，否则递归fa[a],直到找到祖宗节点为止，b也是如此，然后将其返回值判断是否相等

int find(int x)
{if (x == fa[x])return x;elsereturn find(fa[x]);
}

如何合并？

1. 合并时我们应先判断是否最初为一个集合，如果不是，则无需操作
2. 如果不是，我们需要将其中一个元素的父节点赋值为另一个元素即可

int fx=findset(x);
int fy=findset(y);
if(fx==fy)
continue;
else
fa[fx]=fy;

优化如下：

路径压缩：

时间复杂度O（1）

我们可以进行优化，当我们在找寻一个祖宗节点时需要将其元素遍历一遍，挺麻烦的，如果我们能将每个元素和祖宗节点连在一起，就会方便许多，不过它会破坏树的结构

代码：

int find(int x)
{if (fa[x] == x)return x;fa[x] = find(fa[x]);//路径压缩return fa[x];
}

按秩合并：

时间复杂度O（logn）

我们给每一个根节点定一个秩（用rnk数组存储，rnk[i]代表节点i的秩），按秩合并中，当前节点子树的的深度作为树的秩，如果是根节点，秩即为树的深度.此时我们会改变树的结构，不可以再使用路径压缩.

合并集合的时候根节点秩小的集合 合并到秩大的集合，为什么要这么做呢？

图1：

图2：

图3：

当我们将图1中合并时，如果选择将秩大的集合 合并到秩小的集合（即图3），则会使树的结构更长，在数据结构中树的结构短胖才是比较优的，因此我们选择将秩小的集合 合并到秩大的集合（即图2），当查找根节点时更易于查找

但是当两者树的深度一样时，合并以后树的深度需要加1

代码：

int root(int x)
{while(fa[x]^x)//异或在这里等价于！=x=fa[x];return x;
}
void merge(int x, int y)
{x = root(x);y = root(y);if(x == y)return;if(rnk[x] > rnk[y])          //如果x所在树比y所在树深swap(x,y);fa[x]=y;if(rnk[x] == rnk[y])        //如果x所在树与y所在树深相等rnk[y] ++;
}

启发式合并（按大小合并）：

这个与按秩合并道理类似，我们选择将节点较少的集合 合并到较多的集合，这样就是只有较少的点找寻根节点时会多走，此时为最优

代码:

int find(int x)
{while(fa[x]^x)x=fa[x];return x;
}for(int i=1;i<=n;i++)
{fa[i]=i;sz[i]=1;
}
void merge(int x, int y)
{x = find(x);y = find(y);if(x == y)return;if(sz[x] > sz[y])          //如果x所在树节点数大于y所在树节点数swap(x,y);//交换x，ysz[y] += sz[x];            //更新x所在树节点个数fa[x] = y;               //y所在集合合并到x所在集合}

例题：

P3367 【模板】并查集

题意：

有一个并查集，n个元素，m个操作，每次操作给出3个数z,x,y : z为1，将 x与 y所在的集合合并；z为2时，输出x 与y 是否在同一集合内，是的输出 Y ；否则输出 N 。

思路：

模板题，我们直接用我们上文讲到的方法解决即可

代码1（路径压缩）：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int fa[10010];int findset(int x)
{if(fa[x]==x)return x;fa[x]=findset(fa[x]);return fa[x];
}void solve()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++){fa[i]=i;}for(int i=1;i<=m;i++){int x,y,z;cin>>z>>x>>y;if(z==1){int fx=findset(x);int fy=findset(y);if(fx==fy)continue;elsefa[fx]=fy;}else{int fx=findset(x);int fy=findset(y);if(fx==fy)cout<<"Y"<<endl;elsecout<<"N"<<endl;}} return;
}signed main()
{IOSint t;t=1;// cin>>t; while(t--)solve();return 0;
}

代码2（按秩合并）：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int fa[10010];
int rnk[10010];int root(int x)
{while(fa[x]^x)x=fa[x];return x;
}void merge(int x, int y)
{x = root(x);y = root(y);if(x == y)return;if(rnk[x]>rnk[y]) swap(x,y);fa[x]=y;if(rnk[x] == rnk[y])        //如果x所在树与y所在树深相等rnk[y] ++;
}void solve()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++){fa[i]=i;rnk[i]=1;}for(int i=1;i<=m;i++){int x,y,z;cin>>z>>x>>y;if(z==1){merge(x,y); }else{int fx=root(x);int fy=root(y);if(fx==fy)cout<<"Y"<<endl;elsecout<<"N"<<endl;}} return;
}signed main()
{IOSint t;t=1;// cin>>t; while(t--)solve();return 0;
}

注意：不要随意使用rank数组，自定义的rank变量与库中重名

代码（按大小合并）：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int fa[10010];
int sz[10010];int find(int x)
{while(fa[x]^x)x=fa[x];return x;
}void merge(int x, int y)
{x = find(x);y = find(y);if(x == y)return;if(sz[x] > sz[y])          //如果x所在树节点数大于y所在树节点数swap(x,y);//交换x，ysz[y] += sz[x];            //更新x所在树节点个数fa[x] = y;               //y所在集合合并到x所在集合}void solve()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++){fa[i]=i;sz[i]=1;}for(int i=1;i<=m;i++){int x,y,z;cin>>z>>x>>y;if(z==1){merge(x,y); }else{int fx=find(x);int fy=find(y);if(fx==fy)cout<<"Y"<<endl;elsecout<<"N"<<endl;}} return;
}signed main()
{IOSint t;t=1;// cin>>t; while(t--)solve();return 0;
}