并查集被很多OIer认为是最简洁而优雅的数据结构之一，主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作：

合并（Union）：把两个不相交的集合合并为一个集合。
查询（Find）：查询两个元素是否在同一个集合中。

当然，这样的定义未免太过学术化，看完后恐怕不太能理解它具体有什么用。所以我们先来看看并查集最直接的一个应用场景：亲戚问题。

（洛谷P1551）亲戚
题目背景
若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。

题目描述
规定：$x$和$y$是亲戚，$y$和$z$是亲戚，那么$x$和$z$也是亲戚。如果$x,y$是亲戚，那么$x$的亲戚都是$y$的亲戚，$y$的亲戚也都是$x$的亲戚。

输入格式
第一行：三个整数$n,m,p$，（$n\le 5000,m\le 5000,p\le 5000$），分别表示有$n$个人，$m$个亲戚关系，询问$p$对亲戚关系。
以下$m$行：每行两个数$M_i，M_j，1\le M_i，M_j\le N$，表示$M_i$和$M_j$具有亲戚关系。
接下来$p$行：每行两个数$P_i$，$P_j$，询问$P_i$和$P_j$是否具有亲戚关系。

输出格式
$P$行，每行一个’Yes’或’No’。表示第$i$个询问的答案为”具有”或”不具有”亲戚关系。

这其实是一个很有现实意义的问题。我们可以建立模型，把所有人划分到若干个不相交的集合中，每个集合里的人彼此是亲戚。为了判断两个人是否为亲戚，只需看它们是否属于同一个集合即可。因此，这里就可以考虑用并查集进行维护了。

并查集的创建与初始化

一个并查集的元素需要有自己的编号用来代表自己，还需要一个存储一个编号指向父节点，我们可以将这个问题转化到一个数组内，数组的下标就是自己的编号，这个下标的值就是父节点的下标，所以我们一般使用数组来维护并查集：

1	int fa[MAXN];

当然，这个数组里是没有值的，也就是还没有指向自己的父节点，所以我们需要初始化这个数组。由于我们一开始还没有并查集里面各个元素的具体指向，所以我们将并查集指向自己，在数组里就是，每个元素对应的值就是自己的下标。

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

寻找元素根节点

我们可以很简单地用递归的方式寻找根节点：一层一层地访问父节点，直到根节点(根节点的标志就是父节点是元素本身)，要判断两个元素是否属于一个跟节点，只需要判断它们的根节点是否相同即可。

int find(int x){
    if(fa[x] == x) return x;//判读是否是根节点
    else return find(fa[x]);//递归父节点
}

判读是否是一个集合:

1
2
3

if(find(a) == find(b)){
    //...
}

并查集的合并

假设我们有一个并查集如图需要合并：

并查集

这张图的意思是，2指向1，1，3都指向自己,转换到数组可以看做fa[1] = 1,fa[2] = 1,fa[3] = 3

只需要将前者根节点指向后者的根节点就行了。

1
2
3

void merge(int a,int b){
    fa[find(a)] = find(b);
}

效果如图:

合并后的效果

路径压缩

最简单的并查集效率是很低的，如果元素到根节点的距离很远，则需要递归的次数很多。

为了解决这个问题，我们可以使用路径压缩来尽量减少元素到根节点的距离。简单来说，就是将每个节点的父节点设为根节点就好了。

上代码：

int find(int x){
    if(x == fa[x]) return x;
    else{
      fa[x] = find(fa[x]);//将父节点设为递归找到的根节点
      return fa[x];
    }
}

此代码可以简写为一行(三元运算)：

1
2
3

int find(int x){
    return ((x == fa[x])?x:(fa[x] = find(fa[x]));
}

并查集的应用

我们先给出亲戚问题的AC代码：

#include <bits/stdc++.h>
#define MAXN 5003
using namespace std;
int fa[MAXN];

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

int find(int x){
  return ((x == fa[x])?x:(fa[x] = find(fa[x]));
}

void merge(int a,int b){
    fa[find(a)] = find(b);
}

int main(){
    int n,m,p,x,y;
    cin>>n>>m>>p;
    init(n);
    while(m){
        cin>>x>>y;
        merge(x,y);
        m--;
    }
    while(p){
        cin>>x>>y;
        cout<<((find(x) == find (y))?"Yes":"No")<<endl;
        p--;
    }
    return 0;
}