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 ;
}