样例没过&&RE

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;
}