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
超时超时超时.....
1 #include<iostream> 2 #include<stdio.h> 3 #include<cstring> 4 #include<cstdlib> 5 using namespace std; 6 7 int f[1000002]; 8 bool use[1000002]; 9 int cnt; 10 int n,m; 11 int find(int x) 12 { 13 int i=x,r; 14 while(f[x]!=x) 15 x=f[x]; 16 while(i!=x) 17 { 18 r=f[i]; 19 f[i]=x; 20 i=r; 21 } 22 return x; 23 } 24 void Union(int x,int y) 25 { 26 int x1,y1; 27 x1=find(x); 28 y1=find(y); 29 if(x1==y1) return; 30 else 31 { 32 if(x1<n && y1<n) 33 { 34 f[x1]=cnt; 35 f[y1]=cnt++; 36 } 37 else if(x1>=n || y1>=n) 38 { 39 if(x1>=n) 40 f[y1]=x1; 41 else f[x1]=y1; 42 } 43 } 44 } 45 int main() 46 { 47 int i,k,x,y,Num,t=0; 48 char cur[5]; 49 while(scanf("%d%d",&n,&m)>0) 50 { 51 if(n==0&&m==0)break; 52 for(i=0;i<=m;i++) 53 { 54 f[i]=i; 55 use[i]=false; 56 } 57 cnt=n+1; 58 for(i=1;i<=m;i++) 59 { 60 scanf("%s",cur); 61 if(cur[0]=='M') 62 { 63 scanf("%d%d",&x,&y); 64 Union(x,y); 65 } 66 else if(cur[0]=='S') 67 { 68 scanf("%d",&x); 69 f[x]=x; 70 } 71 } 72 Num=0; 73 for(i=0;i<n;i++) 74 find(i); 75 for(i=0;i<n;i++) 76 { 77 k=f[i]; 78 use[k]=true; 79 } 80 for(i=0;i<=m;i++) 81 if(use[i]==true) Num++; 82 printf("Case #%d: ",++t); 83 printf("%d ",Num); 84 } 85 return 0; 86 }