题解(并查集模板) 2018寒假训练1 D.亲戚
zhouwc
2018-02-25 09:47:26
问题 D: 亲戚
时间限制: 1 Sec 内存限制: 128 MB
[提交][状态][讨论版]
题目描述
若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的某个人所在家族的人数。
规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。
输入
第一行：三个整数n，（n<=100,000,m<=200,000），分别表示有n个人，m个信息。
以下m行：信息包含两种形式：
M a b：表示a和b具有亲戚关系。
Q a：要求输出a所在家族的人数。
输出
要求输出a所在家族的人数。
样例输入
5 10
M 3 2
Q 4
M 1 2
Q 4
M 3 2
Q 1
M 3 1
Q 5
M 4 2
Q 4
样例输出
1
1
3
1
4
题解
```cpp
#include<stdio.h>
using namespace std;
int n,m,x,y,f[100005],c[100005];
char t[2];
int find(int x)
{
if (f[x]!=x) f[x]=find(f[x]);
return f[x];
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
{
f[i]=i;
c[i]=1;
}
for (int i=1;i<=m;i++)
{
scanf("%s",&t);
if (t[0]=='M')
{
scanf("%d%d",&x,&y);
int r1=find(x);
int r2=find(y);
if (r1!=r2)
{
f[r1]=r2;
c[r2]=c[r2]+c[r1];
}
} else
{
scanf("%d",&x);
printf("%d\n",c[find(x)]);
}
}
}
```