并查集模板
#include<cstdio>
#include<string>
using namespace std;
const int sz=1e5+1;
int n,m,i,f[sz],s[sz],x,y;
char c[3];
int fd(int x){return f[x]==x?x:f[x]=fd(f[x]);}//查找祖先
int main()
{
scanf("%d%d",&n,&m);
for(i=1;i<=n;++i)f[i]=i,s[i]=1;
while(m--)
{
scanf("%s%d",c,&x);
x=fd(x);
if(c[1]!='2')scanf("%d",&y),y=fd(y);
if(c[0]=='C')
{
y=fd(y);
if(x!=y)//合并联通块
s[x]+=s[y],f[y]=f[x];
}
else
{
if(c[1]=='1')printf("%s\n",x==y?"Yes":"No");
if(c[1]=='2')printf("%d\n",s[x]);
}
}
return 0;
}
注意
if(x!=y)
s[x]+=s[y],f[y]=f[x];
这个判断一定要加一定不能忘记!
因为这个错了之后很难看出来,给的错误的数据要翻半天才能找到。
所以推荐如果这种题目错了直接重做,不细心还想偷懒的后果就是半个小时模板错误找不到。