【BZOJ1015】星球大战

    倒着做操作，并查集维护连通块。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=400010;
inline void read(int &x) {char ch;while ((ch=getchar())<'0' || ch>'9');x=ch-'0';while ((ch=getchar())<='9' && ch>='0') x=x*10+ch-'0';}
 
int head[maxn],next[maxn],E[maxn],Ecnt;
int f[maxn];
int del[maxn],arr[maxn];
int ans[maxn];
int n,m,k,cnt;
 
inline void Add_Edge(int x,int y) {next[++Ecnt]=head[x];head[x]=Ecnt;E[Ecnt]=y;next[++Ecnt]=head[y];head[y]=Ecnt;E[Ecnt]=x;}
 
int Find(int x) {return x==f[x]?x:f[x]=Find(f[x]);}
 
int main()
{
    read(n),read(m);
    for (int i=1,x,y;i<=m;i++) read(x),read(y),Add_Edge(x,y);
    for (int i=0;i<n;i++) f[i]=i,arr[i]=1;
    read(k);
    for (int i=1;i<=k;i++) read(del[i]),arr[del[i]]=0;
    cnt=n-k;
    for (int i=0;i<n;i++) if (arr[i]) for (int j=head[i];j;j=next[j])  if (arr[E[j]] && Find(E[j])!=Find(i)) f[Find(E[j])]=Find(i),cnt--;
    for (int i=k;i;i--)
    {
        ans[i]=cnt++;
        int x=del[i];
        for (int j=head[x];j;j=next[j]) if (arr[E[j]] && Find(x)!=Find(E[j])) f[Find(E[j])]=Find(x),cnt--;
        arr[x]=1;
    }
    ans[0]=cnt;
    for (int i=0;i<=k;i++) printf("%d\n",ans[i]);
    return 0;
}