hdu 2473 Junk-Mail Filter

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define maxn 1100000
 5 using namespace std;
 6 
 7 int f[maxn],num[maxn];
 8 int in[maxn],n,m;
 9 
10 void inti()
11 {
12     for(int i=0; i<n; i++)
13     {
14         f[i]=in[i]=i;
15         num[i]=1;
16     }
17 }
18 
19 int find1(int x)
20 {
21     if(x==f[x]) return x;
22     return f[x]=find1(f[x]);
23 }
24 
25 void merge1(int a,int b)
26 {
27     int fa=find1(a);
28     int fb=find1(b);
29     if(fa!=fb)
30     {
31         f[fa]=fb;
32         num[fb]+=num[fa];
33         num[fa]=0;
34     }
35 }
36 
37 int main()
38 {
39     int ca=1;
40     while(scanf("%d%d",&n,&m)!=EOF)
41     {
42         inti();
43         if(n==0&&m==0) break;
44         getchar();
45         char ch;
46         int ans=n;
47         int u,v;
48         for(int i=1; i<=m; i++)
49         {
50             scanf("%c",&ch);
51             if(ch==‘M‘)
52             {
53 
54                 scanf("%d%d",&u,&v);
55                 merge1(in[u],in[v]);
56             }
57             else if(ch==‘S‘)
58             {
59                 scanf("%d",&v);
60                 int f1=find1(in[v]);
61                 num[f1]--;
62                 in[v]=ans;
63                 f[ans]=ans;
64                 num[ans]=1;
65                 ans++;
66             }
67             getchar();
68         }
69         int t1=0;
70         for(int i=0; i<ans; i++)
71         {
72             if(num[i]>0) t1++;
73         }
74         printf("Case #%d: %d\n",ca++,t1);
75     }
76     return 0;
77 }