P1197 [JSOI2008] 星球大战

rt

#include<bits/stdc++.h>
using namespace std;
struct node{int x,y,next;}bian[400010];
int n,m,k,cnt,head[400010],p[400010],sum;//记录破坏顺序 
int fu[400010],ans[400010];//记录每一次破坏的程度，离线处理 
bool brk[400010];//标记这个点是否被破坏 
void add(int x,int y){
	cnt++;
	bian[cnt].x=x;
	bian[cnt].y=y;
	bian[cnt].next=head[x];
	head[x]=cnt;
}
void build(){
    for(int i=1;i<=n;i++)
        fu[i]=i;
}
int check(int x){
    if(fu[x]==x)return x;
    fu[x]=check(fu[x]);
    return fu[x];
}
int inte(int x,int y){
    x=check(x);
    y=check(y);
    fu[x]=y;
} 
int main(){
	cin>>n>>m;
	build();
	for(int i=1;i<=m;i++){
		int x,y;cin>>x>>y;
		add(x,y);add(y,x); 
	}cin>>k;sum=n-k;
	for(int i=1;i<=k;i++){cin>>p[i];brk[p[i]]=1;}
	for(int i=1;i<=2*m;i++){//预处理破坏到最终程度的连边状态 
		if(brk[bian[i].x]==0&&brk[bian[i].y]==0&&check(bian[k].x)!=check(bian[k].y)){
			//边的起点和终点都完好同时没有联通
			sum--;//减少一个联通块
			inte(bian[i].x,bian[i].y);//连在一起 
		}
	}
	ans[k]=sum;//ans[k]表示第k次打击过后的状态
	for(int i=k;i>=1;i--){//倒序遍历连边 
		sum++;//多了一个点，联通块数量增加
		brk[p[i]]=0;//p[i]没有被破坏
		for(int k=head[p[i]];k;k=bian[k].next){
			if(brk[bian[k].x]==0&&brk[bian[k].y]==0&&check(bian[k].x)!=check(bian[k].y)){
				//边的起点和终点都完好同时没有联通
				sum--;//减少一个联通块
				inte(bian[i].y,bian[i].x);//连在一起 
			}
		} 
		ans[i-1]=sum;
	} 
	for(int i=0;i<=k;i++)
		cout<<ans[i]<<' ';
	return 0;
}