广州C++信奥赛老师解一本通题 1389：亲戚
【题目描述】
若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的某个人所在家族的人数。
规定：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
#include <bits/stdc++.h>
using namespace std;
int tree[100001],member[100001],n,m,q,x,y;
int findParent(int x)
{
///return tree[x]==x? x: findParent( tree[x] ); //如果x的结点的根就是自己，直接返回，否则递归找其父结点
if(tree[x]==x) //如果x的结点的根就是自己，
return x;
else
{
tree[x]=findParent( tree[x] );//路径压缩，否则有2个过，结点不存父结点，直接存放根结点
return tree[x];
}
}
int main()
{
char c;
char s[10];
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
tree[i]=i;
member[i]=1; //刚开始结点的成员数为1
}
for(int i=1;i<=m;i++)
{
scanf(" %c",&c);//注意%c前面有个回车
if(c=='M') //合并操作
{
scanf("%d%d",&x,&y);
int left=findParent(x);
int right= findParent(y);
tree[ right ]= left; //将右边的根挂到左边的根
if(left!=right) //父结点不同，则合并家族成员数量
member[ left ]+= member[ right ];
}
else //输出操作
{
scanf("%d",&x);
printf("%d\n",member[findParent(x)]);
}
}
return 0;
}