ZOJ 2833 Friendship

第一次敲并查集...
 1 #include<cstdio>
 2 #include<memory.h>
 3 int parent[100002];//注意下标值，不然交了会segmentation fault
 4 int find(int i)
 5 {
 6     while(parent[i] >= 0)
 7         i = parent[i];
 8     return i;
 9 }
10 void merge(int i,int j)
11 {
12     int a,b;
13     int temp;
14     a = find(i);
15     b = find(j);
16     if(a!=b)
17     {
18         temp = parent[a] + parent[b];
19         if(parent[b] < parent[a])//parent【b】都为负值，此时表示b这棵树比a这棵树多点
20         {
21             parent[a] = b;  //a为孩子
22             parent[b] = temp;
23         }
24         else
25         {
26             parent[b] = a;
27             parent[a] = temp;
28         }
29     }
30     return ;
31 }
32 int main()
33 {
34     //freopen("input.txt","r",stdin);
35     int n,m;
36     char ch;
37 
38     int count = 1;
39     while(scanf("%d %d",&n,&m)!=EOF)
40     {
41         if(count > 1) printf("
");
42         printf("Case %d:
",count++);
43         memset(parent,-1,sizeof(parent));
44         while(m--)
45         {
46             getchar();//scanf("%d%d",&a,&b);这句你肯定会输入回车的scanf("%c",&ch);这个直接从输入缓冲区读入，也就是那个回车scanf("%c",&ch);
47             scanf("%c",&ch);
48             if(ch == 'M')
49             {
50                 int i,j;
51                 scanf("%d%d",&i,&j);
52                 merge(i,j);
53             }
54             if(ch == 'Q')
55             {
56                 int i,j;
57                 scanf("%d",&i);
58                 j = find(i);
59                 printf("%d
",-parent[j]);
60             }
61         }
62     }
63     return 0;
64 }