合并集合(ACwing836)的代码:
#include <iostream>
using namespace std;
const int N = 100010;
int p[N];
// 集合查询,找到节点x的根节点,并且将查询的这条路径的所有节点都指向他们的根节点
int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
// 初始化集合,每个节点都处在不同的集合当中,共有n个集合
for(int i = 1; i <= n; i ++) p[i] = i;
int x, y;
while(m --)
{
char ch;
cin >> ch >> x >> y;
if(ch == 'M') p[find(x)] = find(y);
else cout << (find(x) == find(y) ? "Yes" : "No") << endl;
}
return 0;
}