bzoj1015：[JSOI2008]星球大战starwar

思路：反着做用并查集维护连通块个数就好了。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

#define maxn 400005

int n,m,tot,k,num;

int now[maxn],pre[maxn],son[maxn],deg[maxn],fa[maxn],ans[maxn];

bool vis[maxn];

inline int read(){

	int x=0;char ch=getchar();

	for (;ch<'0'||ch>'9';ch=getchar());

	for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';

	return x;

}

void add(int a,int b){

	son[++tot]=b;

	pre[tot]=now[a];

	now[a]=tot;

}

void link(int a,int b){

	add(a,b),add(b,a);

}

int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}

int main(){

	n=read(),m=read();

	for (int i=1;i<=n;i++) fa[i]=i;

	for (int i=1,a,b;i<=m;i++) a=read(),b=read(),link(a+1,b+1);

	k=read();

	for (int i=1;i<=k;i++) deg[i]=read(),vis[++deg[i]]=1;

	for (int i=1;i<=n;i++)

		if (!vis[i]){

			num++;

			for (int p=now[i];p;p=pre[p])

				if (!vis[son[p]]){

					int u=find(i),v=find(son[p]);

					if (u!=v) fa[u]=v,num--;

				}

		}

	ans[k+1]=num;

	for (int i=k;i;i--){

		num++;

		for (int p=now[deg[i]];p;p=pre[p])

			if (!vis[son[p]]){

				int u=find(deg[i]),v=find(son[p]);

				if (u!=v) fa[u]=v,num--;

			}

		ans[i]=num,vis[deg[i]]=0;

	}

	for (int i=1;i<=k+1;i++) printf("%d\n",ans[i]);

	return 0;

}