fzu 2155 盟国

Problem 2155 盟国

Accept: 39    Submit: 129
Time Limit: 1000 mSec    Memory Limit : 32768
KB

Problem Description

世界上存在着N个国家，简单起见，编号从0~N-1，假如a国和b国是盟国，b国和c国是盟国，那么a国和c国也是盟国。另外每个国家都有权宣布退盟（注意，退盟后还可以再结盟）。

定义下面两个操作：

“M X Y” ：X国和Y国结盟

“S X” ：X国宣布退盟

Input

多组case。

每组case输入一个N和M (1 ≤ N ≤ 100000 , 1 ≤ M ≤ 1000000),N是国家数，M是操作数。

接下来输入M行操作

当N=0，M=0时，结束输入

Output

对每组case输出最终有多少个联盟，格式见样例。

Sample Input

5 6

M 0 1

M 1 2

M 1 3

S 1

M 1 2

S 3

3 1

M 1 2

0 0

Sample Output

Case #1: 3

Case #2: 2

 

超时超时超时.....

 #include<iostream>

 #include<stdio.h>

 #include<cstring>

 #include<cstdlib>

 using namespace std;

 int f[];

 bool use[];

 int cnt;

 int n,m;

 int find(int x)

 {

     int i=x,r;

     while(f[x]!=x)

         x=f[x];

     while(i!=x)

     {

         r=f[i];

         f[i]=x;

         i=r;

     }

     return x;

 }

 void Union(int x,int y)

 {

     int x1,y1;

     x1=find(x);

     y1=find(y);

     if(x1==y1) return;

     else

     {

         if(x1<n && y1<n)

         {

             f[x1]=cnt;

             f[y1]=cnt++;

         }

         else if(x1>=n || y1>=n)

         {

             if(x1>=n)

                 f[y1]=x1;

             else f[x1]=y1;

         }

     }

 }

 int main()

 {

     int i,k,x,y,Num,t=;

     char cur[];

     while(scanf("%d%d",&n,&m)>)

     {

         if(n==&&m==)break;

         for(i=;i<=m;i++)

         {

             f[i]=i;

             use[i]=false;

         }

         cnt=n+;

         for(i=;i<=m;i++)

         {

             scanf("%s",cur);

             if(cur[]=='M')

             {

                 scanf("%d%d",&x,&y);

                 Union(x,y);

             }

             else if(cur[]=='S')

             {

                 scanf("%d",&x);

                 f[x]=x;

             }

         }

         Num=;

         for(i=;i<n;i++)

             find(i);

         for(i=;i<n;i++)

         {

             k=f[i];

             use[k]=true;

         }

         for(i=;i<=m;i++)

             if(use[i]==true) Num++;

         printf("Case #%d: ",++t);

         printf("%d\n",Num);

     }

     return ;

 }