题目链接

题目大意

给定一个并查集，要求M时合并，要求S时将某点删除出这个集合。问最终有多少集合。

解题思路

利用虚父节点，每次初始化时，n个点的父亲节点不设置成本身，而是连接到新开的虚拟节点。每次删点的时候也仅仅是将其父亲节点改为一个新点。

代码实现

#include<bits/stdc++.h>
using namespace std;

const int N = 1001000;
int n,m,k;
int fa[N*4];
int cnt,ans;
int vis[N*4];

void init(){
    memset(vis,0,sizeof(vis));
    cnt=2*n;
    ans=0;
    for(int i=0;i<n;i++)
        fa[i]=n+i;
    for(int i=n;i<=2*n+m;i++)
        fa[i]=i;
}
int find(int x){
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}
void merge(int x,int y){
    if(find(x)==find(y)) return;
    fa[find(x)]=find(y);
}
void del(int x){
    fa[x]=cnt++;
}
int main(){
    char c;
    int l,r;
    while(1){
        scanf("%d %d",&n,&m);
        if(n==0 && m==0) return 0;
        for(int i=0;i<n;i++) fa[i]=i+n;
        for(int i=n;i<=2*n+m;i++) fa[i]=i;
        memset(vis,0,sizeof(vis));
        ans=0;
        cnt=n*2;
        //init();
        while(m--){
            scanf(" %c",&c);
            if(c=='M'){
                scanf("%d %d",&l,&r);
                merge(l,r);
            }
            if(c=='S'){
                scanf("%d",&l);
                del(l);
            }
        }
        memset(vis,0,sizeof(vis));
        for(int i=0;i<n;i++){
            int faa=find(i);
            if(!vis[faa]){
                ans++;
                vis[faa]=1;
            }
        }
        printf("Case #%d: %d\n",++k,ans);
    }
    return 0;
}