1 //并查集
2 //并查集可以判斷圖的連通性
3 //并查集其實(shí)還有一個(gè)優(yōu)化：就是路徑壓縮:即找到u所在樹(shù)的跟v以后，把從u到v的路徑上的所有點(diǎn)的父親都設(shè)置為v,這樣可以有效的減少查找的時(shí)間
4 //zoj2833
5 #include <iostream>
6 using namespace std;
7 int n,m;
8 int father[100000+1];
9 int f[100000+1];//朋友的個(gè)數(shù)
10 int rank[100000+1];
11 void make_set(int s)
12 {
13 for(int i=1;i<=s;++i)
14 {
15 f[i]=1;
16 father[i]=i;
17 rank[i]=0;
18 }
19 }
20 int find_set(int x)
21 {
22 if(x!=father[x])
23 father[x]=find_set(father[x]);
24 return father[x];
25 }
26 void union_set(int x,int y)
27 {
28 int a=find_set(x);
29 int b=find_set(y);
30 if(rank[a]>rank[b])
31 {
32 father[b]=a;
33 f[a]+=f[b];
34 }
35 else
36 {
37 father[a]=b;
38 f[b]+=f[a];
39 }
40 if(rank[a]==rank[b])rank[b]++;
41 }
42
43 int main()
44 {
45 int a,b;
46 char tmp;
47 int cas=0;
48 while(scanf("%d%d",&n,&m)!=EOF)
49 {
50 if(cas)printf("\n");
51 printf("Case %d:\n",++cas);
52 make_set(n);
53 getchar();
54 for(int i=1;i<=m;++i)
55 {
56 tmp=getchar();
57 if(tmp=='M')
58 {
59 scanf("%d%d",&a,&b);
60 if(find_set(a)!=find_set(b))
61 union_set(a,b);
62 }
63 if(tmp=='Q')
64 {
65 scanf("%d",&a);
66 int sum=f[find_set(a)];
67 printf("%d\n",sum);
68 }
69 getchar();
70 }
71 }
72 return 0;
73 }
74