ps :个人觉得题目有点误导,俩个点之间加一条边不等同于俩个点的祖宗节点相和并,应该题目改为有通路才合理
//
C++ 代码
#include<iostream>
#include<string>
using namespace std;
const int N = 100010;
int p[N],s[N];
int n,m;
int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
int size;
scanf("%d%d",&n,&m);
//将s[]作为节点数量的计算初始为1
for(int i = 0; i < n;i++) p[i] = i,s[i] = 1;
while(m--)
{
string op;
int a,b;
cin >> op;
if(op == "Q1")
{
scanf("%d%d",&a,&b);
if(find(a) == find(b))
puts("Yes");
else puts("No");
}
else if(op == "Q2")
{
scanf("%d",&a);
cout <<s[find(a)]<<endl;
}
else
{
//每次合并都将a祖宗节点所在通路节点数量加b祖宗节点所在通路节点数量
scanf("%d%d",&a,&b);
if(find(a) == find(b)) continue;
s[find(a)] += s[find(b)]; //将b加入到a中
p[find(b)] = find(a); //b的祖宗父节点指向a,即将b所在支线连入a,即b和a之间
//有通路即有边
}
}
return 0;
}