[JSOI2008]星球大战starwar BZOJ1015

#include <cstdio>#include <algorithm>#include <cmath>#include <cstring>#include <cstdlib>#include <iostream>#include <queue>using namespace std;#define N 400005int fa[N<<1],n,m,K,head[N<<1],cnt,q[N],ans[N];struct node{int to,next;}e[N<<1];void add(int x,int y){e[cnt].to=y;e[cnt].next=head[x];head[x]=cnt++;return ;}int find(int x){int p=x,t;while(fa[p]!=p)p=fa[p];while(x!=p)t=fa[x],fa[x]=p,x=t;return p;}bool vis[N];int main(){for(int i=1;i<N;i++)fa[i]=i;memset(head,-1,sizeof(head));memset(vis,1,sizeof(vis));scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);x++,y++;add(x,y);add(y,x);}scanf("%d",&K);ans[K]=n-K;for(int i=1;i<=K;i++){scanf("%d",&q[i]);q[i]++;vis[q[i]]=0;}for(int i=1;i<=n;i++){if(!vis[i])continue;for(int j=head[i];j!=-1;j=e[j].next){int to1=e[j].to;if(!vis[to1])continue;int fx=find(i),fy=find(to1);if(fx!=fy){fa[fx]=fy;ans[K]--;}}}vis[q[K]]=1;for(int i=K-1;i>=0;i--){ans[i]=ans[i+1]+1;for(int j=head[q[i+1]];j!=-1;j=e[j].next){int to1=e[j].to;if(!vis[to1])continue;int fx=find(q[i+1]),fy=find(to1);if(fx!=fy){fa[fx]=fy;ans[i]--;}}vis[q[i]]=1;}for(int i=0;i<=K;i++){printf("%d\n",ans[i]);}return 0;}