C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int p[N];//p[x]存的是x的父节点(parents)
//返回x的根节点
int find(int x)//路径压缩:每次寻找之后都将子节点指向根节点
{
if (p[x] != x)p[x] = find(p[x]);//递归实现while
return p[x];
}
//解析:如果x的父结点!=它本身,则让其父节点=其父节点的父节点
//如此递归下去,最后会使所有具有父节点直接指向其祖先结点(root)
//单个结点本身就是root,多节点的集合除root外均指向root(经过路径压缩之后)
int main()
{
int n, m; cin >> n >> m;
for (int i = 1; i <= n; i++)p[i] = i;
while (m--)
{
char op[2]; int a, b; scanf("%s%d%d", op, &a, &b);//字符串就是字符数组加上结束符 '\0'
//可以使用字符串来初始化字符数组,但此时要注意,每个字符串结尾会暗含一个 '\0' 字符,
//因此字符数组的长度至少要比字符串的长度多 1
if (*op == 'M')
{
p[find(a)] = find(b);//让一方root的父节点=另一方的root
}
else
{
if (find(a) == find(b))puts("Yes");
else puts("No");
}
}
}