[P1197 JSOI2008]星球大战 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

重点：

1.可以离线处理。把在线变为离线。

题意：

有n个点，m条边，有k次操作，每次删去一个点，求每次操作后，还有几个连通块（在同一个并查集中视为是一个连通块）。

分析：

先求出k次操作之后有几个连通块，每次加边，如果不在同一个连通块中，就--ans。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define aa 400010
int n,m,x,y,k,cnt,tot,head[aa],broke[aa],vis[aa],f[aa],ans[aa];
struct node{
    int from,to,next;
}a[aa<<1];
inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')w=-1;
        ch=getchar();
    }
    while(ch<='9'&&ch>='0'){
        s=s*10+ch-'0';
        ch=getchar();
    }
    return s*w;
}
void add(int start,int end){
    ++cnt;
    a[cnt].from =start;
    a[cnt].to =end;
    a[cnt].next =head[start];
    head[start]=cnt;
}
int find(int x){
    if(f[x]==x)return x;
    else return f[x]=find(f[x]);
}
void merge(int x,int y){
    int xi=find(x),yi=find(y);
    if(xi!=yi)f[xi]=yi;
}
int main(){
    n=read();m=read();
    for(int i=1;i<=m;i++){
        x=read();y=read();
        add(x,y);add(y,x);
    }
    k=read();
    for(int i=1;i<=k;i++){
        broke[i]=read();
        vis[broke[i]]=1;
    }
    for(int i=0;i<=n;i++)f[i]=i;
    tot=n-k;
    for(int i=1;i<=cnt;i++){
        if(!vis[a[i].from ]&&!vis[a[i].to ]&&find(a[i].from )!=find(a[i].to )){
            --tot;
            merge(a[i].from ,a[i].to );
        }
    }
    ans[k+1]=tot;
    for(int i=k;i>=1;i--){
        ++tot;
        vis[broke[i]]=0;
        for(int j=head[broke[i]];j!=0;j=a[j].next ){
            if(!vis[a[j].from ]&&!vis[a[j].to ]&&find(a[j].from )!=find(a[j].to )){
                --tot;
                merge(a[j].from ,a[j].to );
                //cout<<a[i].from <<" "<<a[i].to <<" "<<endl;
            }
        }
        //cout<<i<<"              "<<tot<<endl;
        ans[i]=tot;
    }
    for(int i=1;i<=k+1;i++)cout<<ans[i]<<endl;
    return 0;
}