BZOJ 1015 JSOI2008 星球大战

#include <cstdio>#include <vector>#include <algorithm>using namespace std; vector<int>Edge[400005];int x,y,n,m;int k,ban[200005];int fa[400005];bool vis[400005];int tot;int ask[200005]; int find(int x){    if(x!=fa[x]) fa[x]=find(fa[x]);    return fa[x];} void un(int x,int y){    int fx = find(x);    int fy = find(y);    //printf("%d %d %d %d\n",fx,fy,x,y);    if(fx!=fy) tot--,fa[fy]=fx;} int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=m;i++){        scanf("%d%d",&x,&y);        x++;        y++;        Edge[x].push_back(y);        Edge[y].push_back(x);    }    for(int i=1;i<=n;i++) fa[i]=i;    scanf("%d",&k);    for(int i=1;i<=k;i++) scanf("%d",&ban[i]),ban[i]++,vis[ban[i]]=1;    tot = n-k;    for(int i=1;i<=n;i++){        if(vis[i]) continue;        for(int v=0;v<Edge[i].size();v++){            if(vis[Edge[i][v]]) continue;            un(i,Edge[i][v]);        }    }         ask[k+1]=tot;    for(int i=k;i;i--){        vis[ban[i]]=0;        ++tot;        for(int v=0;v<Edge[ban[i]].size();v++){            //printf("Edge[ban[i]][v]:%d\n",Edge[ban[i]][v]);            if(!vis[Edge[ban[i]][v]]) un(ban[i],Edge[ban[i]][v]);        }        ask[i]=tot;    }    //printf("\n");         for(int i=1;i<=k+1;i++){        printf("%d\n",ask[i]);    }    return 0;}