题意：
有N封邮件， 然后又两种操作，
如果是M X Y ， 表示X和Y是相同的邮件。
如果是S X，那么表示对X的判断是错误的，X是不属于X当前所在的那个集合，要把X分离出来，让X变成单独的一个。
最后问集合的个数。
方法一：设立虚父节点
思路：n~n+n-1作为一开始初始化的根节点,而0~n-1作为虚拟根节点(即初试时它们指向n~n+n-1),之后删除节点操作时用n+n-1~n+n+m作为备用节点。
删除时直接修改0~n-1指向的节点(即0~n-1的父亲的值)变为备用节点
设cnt为备用节点，假如一个集合中1是这个集合的父节点(其实是虚的，因为它还指向一开始初始化的n+1，这才是该集合的真正的根节点)。
子节点有2,3，它们分别先指向n+2,n+3,然后都指向实际的根节点即n+1。
1.假如我删除的是1，则我只要令father[1]=cnt，这样2、3指向的还是n+1，它们处于同一个集合内，而1指向的是cnt，已经不处于和2、3同样的集合了。然后cnt++；
2.假如我删除的是2，则我令father[2]=cnt，同样1、3指向的还是n+1，而2的父亲变为cnt，把它们分离开来了。然后cnt++。
求集合个数有两种：用set来求最后集合的个数，640ms；用vis来求最后集合的个数，562ms
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <set> using namespace std;
set<int> group;
int father[];
int vis[];
int n,m,cnt,ans; void init(){
memset(vis,,sizeof(vis));
cnt=*n;
ans=;
for(int i=;i<n;i++)
father[i]=n+i;
for(int i=n;i<=*n+m;i++)
father[i]=i;
group.clear();
} int find_root(int x){
if(father[x]!=x)
father[x]=find_root(father[x]);
return father[x];
}
void Union(int a,int b){
int x=find_root(a);
int y=find_root(b);
father[y]=x;
} int main()
{
char ch[];
int a,b,t=;
while(scanf("%d%d",&n,&m)!=EOF){
if(n== && m==){
break;
}
init();
t++;
for(int i=;i<=m;i++){
scanf("%s",ch);
if(ch[]=='M'){
scanf("%d%d",&a,&b);
Union(a,b);
}
else{
scanf("%d",&a);
father[a]=cnt++; //直接改变它的父亲为备用节点即可。
}
}
/*
for(int i=0;i<n;i++){
int fa=find_root(i);
group.insert(fa);
}
*/
for(int i=;i<n;i++){
int fa=find_root(i);
if(!vis[fa]){
ans++;
vis[fa]=; //fa为一个根节点，之后如果还有点的根节点为fa，表明在同一个集合中，不用再重复加了。
}
} //printf("Case #%d: %d\n",t,group.size());
printf("Case #%d: %d\n",t,ans);
} return ;
}
方法二：穿个马甲/找个代理：
思路：当要删除x点时，不是真的删除x点， 而是通过映射方式（这里用数组majia[N]），把x变成一个新的点即majia[x]=cnt.
看到网上有这么解释的：用了代理majia[i]表示i的代理是majia[i]，然后以后操作的时候每个人干活只找代理干,即查找、合并传递的参数都是majia[i]，而不是i。
然后删除的时候直接换个新代理（这个代理不能和别人的代理冲突),majia[i]=cnt++;
设cnt备用点，假如一个集合中1是这个集合的父节点，子节点有2,3。合并的时候传递的其实是majia[1],majia[2],majia[3], 但是因为他们一开始即是本身，所以和传统的并查集没什么不同。
目前father[1]=1,father[2]=1,father[3]=1,majia[1/2/3]=majia[1/2/3]
1.假如我删除的是1，则我只要令majia[1]=cnt++;这样如果以后我想要查找1的根节点时，我实际上传递的值为cnt，而father[cnt]=cnt，因此相当于1的根节点变为n了。
而查找2、3的根节点时，传递的还是2、3，所以实际上等同于1和2、3分离了。
然后假如1和4合并，那么传递的其实值为(majia[1],majia[4])，即(cnt,4)，那么father[cnt]=4，即1、4的根节点为4.
2.假如我删除的是2，则我令majia[2]=cnt，此时，我若查找2的根节点，传递的参数为cnt，则结果为cnt，不为1。也就相当于2从1所在的集合删去了。
2还是2，只不过相当于穿了一层外套，换了另一种身份，我们用这种身份来表示2。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <set> using namespace std; set<int> group; //可以用set来获取集合个数(因为set里元素不可重复)
int father[];
int majia[]; //代理，或者理解为第二个身份
int vis[]; //最后用于获取集合个数
int n,m,cnt,ans; void init(){
memset(vis,,sizeof(vis));
cnt=n;
ans=;
for(int i=;i<=n+m;i++)
father[i]=majia[i]=i;
group.clear();
} int find_root(int x){
if(father[x]!=x)
father[x]=find_root(father[x]);
return father[x];
}
void Union(int a,int b){
int x=find_root(a);
int y=find_root(b);
father[y]=x;
} int main()
{
char ch[];
int a,b,t=;
while(scanf("%d%d",&n,&m)!=EOF){
if(n== && m==){
break;
}
init();
t++;
for(int i=;i<=m;i++){
scanf("%s",ch);
if(ch[]=='M'){
scanf("%d%d",&a,&b);
Union(majia[a],majia[b]); //操作时，即传递参数，都是用它的代理/第二身份
}
else{
scanf("%d",&a);
majia[a]=cnt++; //改变它的代理/第二身份。
}
}
for(int i=;i<n;i++){
int v=find_root(majia[i]);
if(!vis[v]){
ans++;
vis[v]=;
}
} //printf("Case #%d: %d\n",t,group.size());
printf("Case #%d: %d\n",t,ans);
} return ;
}