BZOJ [JSOI2008]星球大战starwar

 1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=4e6+10; 4 bool del[N],v[N]; 5 int f[N],p[N],head[N],cnt,tot,ans[N],n,m,k; 6 int get(int x){return x==f[x]?x:f[x]=get(f[x]);} 7 struct node{ 8 ????int to,nex; 9 }e[N];10 void addd(int x,int y){e[++cnt].to=y;e[cnt].nex=head[x];head[x]=cnt;}11 void add(int x)12 {13 ????int fx=get(x);14 ????for(int i=head[x];i;i=e[i].nex)15 ????{16 ????????int y=e[i].to;17 ????????if(v[y])18 ????????{19 ????????????int fy=get(y);20 ????????????if(fy!=fx)f[fy]=fx,tot--;21 ????????}22 ????}23 }24 int main()25 {26 ????scanf("%d%d",&n,&m);int x,y;27 ????for(int i=1;i<=n;++i)f[i]=i;28 ????for(int i=1;i<=m;++i)29 ????{30 ????????scanf("%d%d",&x,&y);31 ????????addd(x,y);addd(y,x);32 ????}33 ????scanf("%d",&k);34 ????for(int i=1;i<=k;++i)35 ????{36 ????????scanf("%d",&p[i]);37 ????????del[p[i]]=1;38 ????}39 ????for(int i=0;i<n;++i)40 ????{41 ????????if(!del[i])42 ????????{43 ????????????tot++;44 ????????????add(i);45 ????????????v[i]=1;46 ????????}47 ????}48 ????ans[0]=tot;49 ????for(int i=k;i;--i)50 ????{51 ????????tot++;52 ????????add(p[i]);53 ????????v[p[i]]=1;54 ????????ans[k-i+1]=tot;55 ????}56 ????for(int i=k;i>=0;--i)printf("%d\n",ans[i]);57 ????return 0;58 }