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 Sample Output//812 ms 17816KB
#include<stdio.h>
#include<string.h>
#define M 1000000<<1
int pre[M],real[M];
bool vis[M];
int n,m;
/* 超时
int find(int x)
{
while(x!=pre[x])
x=pre[x];
return x;
}
*/
int find(int cur)
{
return pre[cur]==cur?cur:pre[cur]=find(pre[cur]);
}
int main()
{
int cas=1;
while(scanf("%d%d",&n,&m),n|m)
{
for(int i=0; i<n; i++)
pre[i]=real[i]=i;
memset(vis,0,sizeof(vis));
int a,b,k=n;
while(m--)
{
getchar();
char s;
scanf("%c",&s);
if(s==‘M‘)
{
scanf("%d%d",&a,&b);
int x=find(real[a]);
int y=find(real[b]);
if(x!=y)pre[x]=y;
}
else
{
scanf("%d",&a);
pre[k]=k;
real[a]=k++;//记录新的位置
}
}
int ans=0;
for(int i=0; i<n; i++)
{
int x=find(real[i]);
if(!vis[x])
{
vis[x]=1;
ans++;
}
}
printf("Case #%d: %d\n",cas++,ans);
}
return 0;
}
fzu 2155 盟国 并查集的增删,布布扣,bubuko.com
原文：http://blog.csdn.net/crescent__moon/article/details/22855763