一、并查集的作用
- 将两个集合合并
- 询问两个元素是否在同一个集合当中
二、并查集的基本原理
每个集合用一棵树来表示。树根的编号就是整个集合的编号。每个节点存储它的父节点，p[x]表示x的父节点
- 如何判断树根：if(p[x]==x)
- 如何求x的集合编号：while(p[x]!=x) x=p[x];
- 如何合并两个集合：px是x的集合编号，py是y的集合编号，p[x]=y
三、实现
#include <iostream>
using namespace std;
const int N = 100010;
int p[N], n, m;
int find(int x) //返回x所在集合的编号+路径压缩
{
if (p[x] != x) //如果这个点不是根节点（如果不是自己指向自己）
p[x] = find(p[x]); //x的父节点就是find的返回值（find求的就是根节点，其实这里就是把x的父节点直接当作根节点，这就叫路径压缩）
return p[x];
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
p[i] = i;
while (m--)
{
char op[2];
int a, b;
cin >> op >> a >> b;
if (op[0] == 'M')
{
p[find(a)] = find(b); //合并操作，将a所在集合的根节点的父节点设成b的根节点
}
else
{
if (find(a) == find(b))
cout << "Yes\n";
else
cout << "No\n";
}
}
return 0;
}