学步园

并查集删点问题，牺牲空间换取时间，就是给每一个点找一个替代，删除的时候只需要把替代更换就可以了

code：

#include <cstdio>
#include <cstring>
using namespace std;

const int INF = 0x3fffffff;

int n,m,fa[1000000],rank[100000],rep[1000000],ind;
bool vis[1100000];

void init()
{
    for(int i=0;i<n;i++)
    {
        fa[i]=i;
        rank[i]=0;
        rep[i]=i;//刚开始i的代替就是i自己
    }
    ind=n;
}
int find(int k)
{
    if(k!=fa[k])
    {
        fa[k]=find(fa[k]);
    }
    return fa[k];
}
void merge(int x,int y)
{
    if(x==y)
    {
        return ;
    }
    if(rank[x]<rank[y])
    {
        fa[x]=y;
    }else{
        fa[y]=x;
        if(rank[x]==rank[y])
        {
            rank[x]++;
        }
    }
}
void del(int k)//替代删除,只更改它的替代就可以
{
    rep[k]=ind;
    fa[ind]=ind;//初始化集合
    ind++;
}

char c;
inline void scan(int &x){
    while(c=getchar(),c<'0'||c>'9');
    x=c-'0';
    while(c=getchar(),c>='0'&&c<='9')x=x*10+c-'0';
}

int main()
{
    int cas=0,a,b,i;
    char buf;
    while(~scanf("%d%d",&n,&m) && (n || m))
    {
        init();
        getchar();
        for(i=1;i<=m;i++)
        {
            buf=getchar();
            if(buf=='M')
            {
                scan(a);
                scan(b);
                a=find(rep[a]);
                b=find(rep[b]);
                merge(a,b);
            }else{
                scan(a);
                del(a);
            }
        }
        b=0;
        memset(vis,false,sizeof(int)*(ind+1));
        for(i=0;i<n;i++)
        {
            a=find(rep[i]);
            if(!vis[a])
            {
                b++;
                //printf("%d\n",a);
                vis[a]=true;
            }
        }
        printf("Case #%d: %d\n",++cas,b);
    }
    return 0;
}