1389：亲戚

http://ybt.ssoier.cn:8088/problem_show.php?pid=1389
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n, m, a, b;
 4 char c;
 5 struct qq{
 6     int fa;//团伙头领 
 7     int cnt;// 团伙人数 
 8 };
 9 qq f[100010]; 
10 void init()
11 {
12     for(int i=1; i<=n; i++){
13         f[i].fa=i;//初始化团伙头领就是自己 
14         f[i].cnt=1;//初始化团伙人数为1 
15     }
16 }
17 int find(int x){//路径压缩查找头领 
18     if(f[x].fa!=x)
19         f[x].fa=find(f[x].fa);
20     return f[x].fa;
21 }
22 void merge(int x, int y){
23     int xx=find(x);
24     int yy=find(y);
25     if(f[xx].fa!=yy){//避免像样例中数据的重复输入相同关系 
26         f[xx].fa=yy;
27         f[yy].cnt+=f[xx].cnt;//头领所在团伙人数  累加上  原团伙头领所在团伙的人数 
28     }    
29 }
30 int main()
31 {
32     scanf("%d%d",&n, &m);
33     init();
34     while(m--){
35         scanf(" %c",&c);//注意%c前面有个空格 
36         if(c=='M'){
37             scanf("%d%d",&a, &b);
38             merge(a, b);//合并罪犯 
39         }
40         if(c=='Q'){
41             scanf("%d",&a);
42             int fa=find(a);//找头领 
43             int ans=f[fa].cnt;//头领的团伙人数 
44             printf("%d
",ans);
45         }
46     }
47     return 0;
48  }