今天我们来介绍一下并查集
那么什么是并查集呢
我们来看看百度百科是怎么介绍的，emmm，好像不太能理解。其实就是一个个不相交的集合之间的合并与查询等相关问题的解决方法，这些集合可以想象成一颗颗树。
初始的时候集合里只有一个元素，通过不断地合并形成一个拥有很多元素的集合，比如一个家族中有非常多成员，但是和你有血缘关系的人也就那些，他们之间可以构成一个集合也就是一颗树，树的根节点就是这群人中辈分最大的那一个人，然后一直往下排。如果我们想要判断两个人是否是亲戚关系，那么我们就要判断他们的根节点是不是一样的，也就是查询操作。有时候我们需要合并两个集合，如果只是简单的寻找一个树的根节点，然后让另一颗树变成它的子树的话，在数据非常大的时候效率会非常低，然后现在有两个方法可以解决这一个问题，分别是路径压缩和按秩合并。这里我们只介绍路径压缩方法
首先我们来看看查找函数怎么实现
先将树的根节点初始化
// p数组存每棵树的根节点
int p[MAXN];
void init(int n)
{
for (int i = 1; i <= n; ++i)
p[i] = i;
}
接着我们写一下查询函数
//正常的查询
int find(int x)
{
if(fa[x] == x) return x;
else return find(fa[x]);
}
//结合路径压缩的查询
// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
最后就是合并了(路径压缩)
//因为查询的时候就已经实现了路径压缩，所以这里就直接查询并合并即可
void merge(int i, int j)
{
p[find(i)] = find(j);
}
现在我们来讲一下路径压缩是怎么实现的
一般来说我们都是一层一层的往上找，然后找到根节点，那么怎么样才能快速找到根节点呢。其实只要查询的时候当前节点不是根节点，我们就让其指向根节点，这样每一条超根节点的路径上的点都直接指向了根节点，就不需要层层查询了，达到了路径压缩的效果
现在我们来做一道模板题吧
题目描述
一共有 n 个数，编号是 1∼n，最开始每个数各自在一个集合中。
现在要进行 m 个操作，操作共有两种：
M a b，将编号为 a 和 b 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；
Q a b，询问编号为 a 和 b 的两个数是否在同一个集合中；
输入格式
第一行输入整数 n 和 m。
接下来 m 行，每行包含一个操作指令，指令为 M a b 或 Q a b 中的一种。
输出格式
对于每个询问指令 Q a b，都要输出一个结果，如果 a 和 b 在同一集合内，则输出 Yes，否则输出 No。
每个结果占一行。
数据范围
$1≤n,m≤105$
输入样例：
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4
输出样例：
Yes
No
Yes
C++
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 100010;
int n , m;
int p[N];
int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main ()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) p[i] = i;
while (m -- )
{
char s[2];
int a , b;
scanf("%s%d%d" , s , &a , &b);
if(s[0] == 'M') p[find(a)] = find(b);
else
{
if(find(a) == find(b)) puts("Yes");
else puts("No");
}
}
return 0;
}
引用
简单百度了一下，发现其他大佬介绍的很他妈详细，所以在这里提供一下链接避免小伙伴走错房间，hhh
