BZOJ 1015, 星球大战

Problem

传送门

Mean

编写一个支持删点并查询当前图中连通块个数的数据结构。

Analysis

离线倒序处理+并查集。
于是删点就变成了加点，因此不必考虑正序处理时删边后两点是否仍连通的问题。
先将所有未删除的点加入到图中，再倒序依次加入被删除的点，用并查集来维护图的连通块个数。

Code

#include<cstdio>
const int M=400005;
int n,m,k,x,y,ed,cnt,f[M],v[M],nxt[M],g[M],od[M],ans[M];
bool p[M],in[M];
void addedge(int x,int y){
    v[++ed]=y;
    nxt[ed]=g[x];
    g[x]=ed;
}
int find(int x){return f[x]!=x?f[x]=find(f[x]):x;}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++) f[i]=i;
    while(m--) scanf("%d%d",&x,&y),addedge(x,y),addedge(y,x);
    scanf("%d",&k);
    for(int i=0;i<k;i++) scanf("%d",&od[i]),p[od[i]]=1;
    for(int i=0;i<n;i++) if(!p[i]){
        cnt++;in[i]=1;
        int a=find(i),b;
        for(int j=g[i];j;j=nxt[j]) if(in[v[j]]){
            b=find(v[j]);
            if(a!=b){f[b]=a;cnt--;}
        }
    }
    ans[k]=cnt;
    for(int i=k-1;i>=0;i--){
        cnt++;in[od[i]]=1;
        int a=find(od[i]),b;
        for(int j=g[od[i]];j;j=nxt[j]) if(in[v[j]]){
            b=find(v[j]);
            if(a!=b){f[b]=a;cnt--;}
        }
        ans[i]=cnt;
    }
    for(int i=0;i<=k;i++) printf("%d\n",ans[i]);
    return 0;
}