1 /*
 2 Author:    Leo.W
 3 Descriptipn:  一個垃圾郵件判別系統(tǒng)。M a b 表示a、b具有相同內(nèi)容，S a 表示對a存在誤判，求最后內(nèi)容相同郵件集合的數(shù)目。
 4 How to Do:    并查集，加入了一個新的操作是集合節(jié)點(diǎn)的刪除，但由于集合內(nèi)部元素關(guān)系的傳遞性，因此刪除元素但保留由此元素
 5               帶來的關(guān)系。所以不必刪除結(jié)點(diǎn)，直接改頭換面讓被刪除的結(jié)點(diǎn)在隊(duì)末出現(xiàn)，重新開始，因此就用到了id數(shù)組。
 6   */
 7 #include <cstdio>
 8 #include <cstdlib>
 9 #define MAXSIZE 1000002
10 int n,m;//n個結(jié)點(diǎn)，m條路
11 int par[MAXSIZE],id[MAXSIZE],hasChild[MAXSIZE];
12 char ch;
13 
14 int findSet(int x){
15     if(x!=par[x])
16         par[x]=findSet(par[x]);
17     return par[x];
18 }
19 inline void merge(int x,int y){
20     x=findSet(x);
21     y=findSet(y);
22     if(x==y) return;
23     par[x]=y;//x變成附屬
24     hasChild[y]+=hasChild[x];
25     hasChild[x]=0;//表示x只是y領(lǐng)銜的集合的一員
26 }
27 inline void makeSet(int n){
28     int i;
29     for(i=0;i<n;i++)//從0到n-1
30         par[i]=i,id[i]=i,hasChild[i]=1;
31 }
32 inline void scan(int &x){
33     while (ch=getchar(),ch<'0'||ch>'9');x=ch-'0';
34     while (ch=getchar(),ch>='0'&&ch<='9')x=x*10+ch-'0';
35 }
36 int main(){
37     //freopen("in.txt","r",stdin);
38     int no=1;
39     while (true){
40         scan(n);scan(m);
41         if(n==0&&m==0)    break;
42         makeSet(n);
43         int i,j;  int total=n;//用于隊(duì)末擴(kuò)展
44         char str;    int a,b;
45         for(i=0;i<m;i++){
46             str=getchar();
47             scan(a);
48             if(str=='M'){            
49                 scan(b);
50                 merge(id[a],id[b]);
51                 continue;
52             }
53             int fa=findSet(id[a]);
54             hasChild[fa]--;//原屬集合內(nèi)部元素?cái)?shù)減少
55             id[a]=total;//映射被刪除的結(jié)點(diǎn)，以后對a的操作，轉(zhuǎn)為對total的操作
56             par[total]=total;//自立門戶，即單獨(dú)一個集合
57             hasChild[total]=1;
58             id[total]=total;//擴(kuò)展方便最后統(tǒng)計(jì)
59             total++;
60         }
61         int sum=0;
62         for(j=0;j<total;j++)
63             if(hasChild[j]>0)    sum++;
64         printf("Case #%d: %d\n",no++,sum);
65     }    
66     return 0;
67  }
68