亲戚——高级

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 299		Accepted: 129

Description

若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的某个人所在家族的人数。
规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。

Input

第一行：三个整数n，（n<=100,000,m<=200,000），分别表示有n个人，m个信息。
以下m行：信息包含两种形式：
M a b：表示a和b具有亲戚关系。
Q a：要求输出a所在家族的人数。

Sample Input

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

Sample Output

1 1 3 1 4

#include <stdio.h>
#include <string.h>
struct A
{
  int s;
  int sl;
};
struct A a[100001];
int main()
{
    int n,m,y,z,x,k;
    char r;
    for(int i=1;i<=100001;i++)
    {
      a[i].s=i;a[i].sl=1;
    }
    while(scanf("%d%d",&n,&m)!=EOF)
    {
      getchar();
      for(int i=1;i<=m;i++)
      {
        scanf("%c",&r);
        getchar();
        if(r=='M')
        {
          scanf("%d%d",&z,&y);getchar();
          while(a[z].s!=z){z=a[z].s;}\\寻找初始地址也就是亲戚数所存的位置
          while(a[y].s!=y){y=a[y].s;}          
          if(a[z].s!=a[y].s)
          {
          if(a[a[z].s].sl>a[a[y].s].sl){x=a[z].s;k=a[y].s;}
          else{x=a[y].s;k=a[z].s;}
          a[a[y].s].s=x;
          a[a[z].s].s=x;
          if(x!=k){a[x].sl+=a[k].sl;}
          else{a[x].sl++;}
          }
        }
        if(r=='Q'){scanf("%d",&x);getchar();while(a[x].s!=x){x=a[x].s;}printf("%d\n",a[a[x].s].sl);}
      }
    }
  return 0;                                                   
}

让所有亲戚的值放在1个地址上，然后所有该人的亲戚的亲戚数位置指向该人地址