题目大意:输入两个整数n，m(n表示点的个数,m表示操作数)。在接下来的m行中,对点的操作有两种
1)M a b 。 表示将a、b并到一个集合中
2)S a .表示将a从原来的集合中去除，而成为一个单独的集合
解题思路:并查集
1)
解题思路:并查集，M代表合并，S代表删除，下面讲一下删除操作
大家都知道合并操作就是找到找到两个节点的父亲，修改父亲，如果删除就是将该点的父亲重新设置成自己，这样行不行呢？
这是不行的，比如1，2，3的父亲都是1，现在删除1，1的父亲还是1，2,3也是1，集合还是1个，正确的应该是2个。
那删除节点的父亲不设成自己给新申请一个节点当做父亲，比如1,2,3的父亲都是1，在一个集合，现在删除1，申请了4当做1的父亲，2,3父亲都是1，然后Find(2)找2的父亲
2的父亲是1，但是1的父亲是4，所以给2的父亲更新成了4,3同理，所以还不行。
正确的方法是每一个点都设立一个虚拟父亲比如1,2,3的父亲分别是4,5,6，现在合并1,2,3都在一个集合，那他们的父亲都是4，现在删除1，那就给1重新申请一个节点7
现在2,3的父亲是4,1的父亲是7，删除成功。
2)定义数组 int[] father
int[] rank
father[i]=i,则i表示本集合且i是集合对应的树的根
father[i]=j,则表示j是i的父节点
rank[i]代表集合i的秩(比如子孙的多少或树的高度等），用于合并集合，秩小的合并到秩大的。
3)
开始让我混淆的一个地方是，假设如下情况
M 0 2
M 1 2
S 2
那么按照并查集来做， 0指向2， 1指向2，即
0 -->2
1 -->2 ,
那么删除2之后，我以为题目意思是所有与2有关系的都要删除， 那么这两个关系都要去掉， 又变成独立的3个了。
但是我这种理解是错的。 合并起来后就是一个集合{0,1,2}， 如果把2删除掉之后， {0，1}还是集合。
理解题意之后， 我们知道用并查集来构造集合是很容易的，但是要把集合中的一个删掉，却很不容易。 通过这题，我学习到了所谓的设立需父节点的方法。
关键的过程是假设要删除x点， 那么不是真的删除x点， 而是通过一个映射（这里用数组majia[N]），把x变成一个新的点即majia[x] = newNode.那么， 原来的那些集合还是不变，只是少了个x点。
-----------------------------------------------------------------------------------------------------
以下代码是根据解题思路1)写出来的。
代码如下:
/*
* 2473_4.cpp
*
* Created on: 2013年8月23日
* Author: Administrator
*/ #include <iostream> using namespace std; int father[1100000];
bool flag[1000050];
int id; int find(int x){
int r,i,j; r = x;
while( r!= father[r]){
r = father[r];
} i = x;
while(i!=r){
j = father[i];
father[i] = r;
i = j;
} return r;
} /**find(int a) 也可以写成以下形式:
int find(int a){
if(a != father[a]){
father[a] = find(father[a]);
} return father[a];
}
*/
void join(int x , int y){
int fx = find(x);
int fy = find(y); if(fx != fy){
father[fx] = fy;
}
} void make_set(int n , int m){
int i;
for(i = 0 ; i < n ; ++i){
father[i] = i + n;
} for(i = n ; i <= n + n + m ; ++i){
father[i] = i;
}
} void delete_set(int x){
father[x] = id++;
} int main(){
int n,m,count = 1;
while(scanf("%d%d",&n,&m)!=EOF,n||m){
int i;
id = n + n;
make_set(n,m);//****千万别漏了
for( i = 0 ; i < m ; ++i){
int a,b;
char c[5];
scanf("%s",c);
if(c[0] == 'M'){
scanf("%d%d",&a,&b);
join(a,b);
}else if(c[0] == 'S'){
scanf("%d",&a);
delete_set(a);
}
} memset(flag,0,sizeof(flag));
int ans = 0;
for( i = 0 ; i < n ; ++i){
int x = find(i);
if(!flag[x]){
ans++;
flag[x] = true;
}
} printf("Case #%d: %d\n",count++,ans); }
}