让我们先看一道题

题目

或许你不知道，你的某个朋友是你的亲戚。他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子。如果能得到完整的家谱，就可以判断两个人是否亲戚，但如果两个人的最近公共祖先与他们相隔好几代，使得家谱十分庞大，那检验亲戚关系实非人力所能及。

在这种情况下，最好的帮手就是计算机。你将得到一些亲戚关系的信息，如同Marry和Tom是亲戚，Tom和Ben是戚，等等。从这些信息中，你可以推出Marry和Ben 是亲戚。

请写一个程序，对于亲戚关系的提问，快速给出答案。

输入

输入由两部分组成：

第一部分以N，M开始。N为问题涉及的人的个数(1 ≤ N ≤ 20000)。这些人的
编号为1,2,3,…,N。下面有M行(1 ≤ M ≤ 100000)，每行有两个数ai, bi，表示
已知ai和bi是亲戚。
第二部分以Q开始。以下Q行有Q个询问(1 ≤ Q ≤ 1 000 000)，每行为ci,di，表示询问ci和di是否为亲戚。对于每个询问ci, di，若ci和di为亲戚，则输出Yes，否则输出No。

Input

10 7
2 4
5 7
1 3
8 9
1 2
5 6
2 3
33
4
7 10
8 9

Output

Yes
No
Yes

思路

看到这里可以考虑floyd之类的，但是很明显时间复杂度O(n^3)，不可行
这是一道并查集板题，让我们了解一下

并查集的引入

并查集是一种树形结构，用来处理几个不相交集合的查询与合并的问题
他的主要可以实现的功能是

1.合并两个不相交的树形结构
2.查看两个元素是否在同一个结构内

看到这里，如果能实现以上功能，开头的引子就迎刃而解了
让我们看看如何实现

并查集如何实现

路径压缩/查询操作

在一棵树里，如果判断两个元素是否在同一个集合里，只需要判断他们的根节点是否相同即可。这样就需要O（n）的复杂度来完成这件事
路径压缩就是把所有的节点的父亲都设立为根节点（这样我们就只用每次查询这两个节点的父亲就好了）

注：括号中为当前节点的父亲标记
代码怎么实现呢？
可以先找到根节点，然后再从根节点往下递归，同时把每个递归到的节点的父亲设置为根节点

代码实现路径压缩/查询

int getfather(int x){
    if(father[x]==x)return x;
    else {
        father[x]=getfather(father[x]);
        return father[x];
    }
}

操作合并

假如有两棵树
要把这两棵树合并起来非常方便

先判断这两颗树是不是同一棵树，这时可以用到的是前面的getfather函数

图片说明

int fx=getfather(x);
int fy=getfather(y);
if(fx==fy)return true;

如果不是的话
图片说明

这里传入两个节点x,y，fx为x的根节点，fy为y的根节点，那么若fx==fy即两个根节点相同，可以知道两个节点在同一个集合里，返回true

否则将这两个元素所在的集合合并

合并方法：将两个元素分别的根节点之间连一条边就好

else {
  father[fx]=fy;
  return false;
}

然后就实现了

代码完整实现合并

bool reger(int x,int y){
  int fx=getfather(x);
  int fy=getfather(y);
  if(fx==fy)return true;
  else {
      father[fx]=fy;
      return false;
  }
}

让我们回到开始

有了刚刚的两个函数getfather和reger，可以轻而易举的解出这道题

准备：初始化
```
for(int i=1;i<=n;i++)father[i]=i;
```

第一组：建边

for(int i=1;i<=m;i++){
  int x,y;
  cin>>x>>y;
  reger(x,y);
}

第二组：查询

for(int i=1;i<=q;i++){
  int x,y;
  cin>>x>>y;
  if(getfather(x)==getfather(y))f[i]=true;
  else f[i]=false;
}

附上完整代码

#include<iostream>
using namespace std;
int father[200005],n;
bool f[1000005];
int getfather(int x){
  if(father[x]==x)return x;
  else {
      father[x]=getfather(father[x]);
      return father[x];
  }
}
bool reger(int x,int y){
  int fx=getfather(x);
  int fy=getfather(y);
  if(fx==fy)return true;
  else {
      father[fx]=fy;
      return false;
  }
}
int main(){
  int m,q;
  cin>>n>>m;
  for(int i=1;i<=n;i++)father[i]=i;
  for(int i=1;i<=m;i++){
      int x,y;
      cin>>x>>y;
      reger(x,y);
  }
  cin>>q;
  for(int i=1;i<=q;i++){
      int x,y;
      cin>>x>>y;
      if(getfather(x)==getfather(y))f[i]=true;
      else f[i]=false;
  }
  for(int i=1;i<=q;i++){
      if(f[i])cout<<"yes"<<endl;
      else cout<<"no"<<endl;
  }
  return 0;
}

写在最后

如有错误，欢迎大家指出~~
附上一个好用的画图工具 CS Academy

并查集基础用法[NKOJ亲戚]