AcWing 836. 合并集合_注释
原题链接
简单
作者:
很自然的事
,
2022-11-30 21:23:43
,
所有人可见
,
阅读 120
#include <iostream>
using namespace std;
const int N = 100010;
int p[N]; // 开p数组储存结点x的父节点
int find(int x)
{
if (p[x] != x)
//这一步,找祖宗结点 + 路径压缩,太喵了!
p[x] = find(p[x]);
return p[x];
}
int main()
{
int n, m;
cin >> n >> m;
// 初始化 1-n 个数的父节点都是自己
for (int i = 1; i < n; i++)
p[i] = i;
while (m --)
{
char op[2];
scanf("%s", op);
int a, b;
cin >> a >> b;
if(*op == 'M')
p[find(a)] = find(b); //找到 a,b 的祖宗结点,再将 a 的父节点连接到 b 上
else
{
if (find(a) == find(b))
cout << "Yes" << endl;
else
cout << "No" << endl;
}
}
return 0;
}