记录编号	272899	评测结果	AAAAAAAAAA
题目名称	[JSOI 2008]星球大战starwar	最终得分	100
用户昵称	SOBER GOOD BOY	是否通过	通过
代码语言	C++	运行时间	0.840 s
提交时间	2016-06-18 11:08:07	内存使用	34.56 MiB

#include<cstring>
#include<iostream>
#include<algorithm>
#include<stack>
#include<cstdio>
using namespace std;
const int maxn=200610;
int n,m;
struct Edge
{
	int x,y;	
}e[maxn*8];
struct dege
{
	int next;
	int to;
}E[maxn*8];
int K,a[maxn*3];
int fa[maxn*3],ans[maxn*3],head[maxn*3];
bool f[maxn*3];
int len=0;
int Find(int x)
{
	if(fa[x]!=x)
	{
		fa[x]=Find(fa[x]);
	}
	return fa[x];
}
void Insert(int x,int y)
{
	len++;
	E[len].to=y;
	E[len].next=head[x];
	head[x]=len;
}
int main()
{
	freopen("bzoj_1015.in","r",stdin);
	freopen("bzoj_1015.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&e[i].x,&e[i].y);
		e[i].x++;
		e[i].y++;
		Insert(e[i].x,e[i].y);Insert(e[i].y,e[i].x);
	}
	scanf("%d",&K);int hh=n;
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=K;i++)
	{
		scanf("%d",&a[i]);
		a[i]++;hh--;
		f[a[i]]=1;
	}
	for(int i=1;i<=len;i++)
	{
		if(f[e[i].x]||f[e[i].y])continue;
			int	rtx=Find(e[i].x),rty=Find(e[i].y);
			if(rtx!=rty)
			{
				fa[rty]=rtx;
				hh--;	
			}
	
	}
	ans[0]++;
	ans[ans[0]]=hh;
	int x,y;
	for(int i=K;i>=1;i--)
	{
		x=a[i];
		int rtx=Find(x);
		hh++;
		for(int j=head[x];j;j=E[j].next)
		{
			int t=E[j].to;
			if(f[t]) 
			continue;
			y=Find(t);
			if(y!=rtx)
			{
				hh--;
				fa[y]=rtx;
			} 
		}f[x]=0;
		ans[0]++;
		ans[ans[0]]=hh;
	}
	for(int i=ans[0];i>=1;i--)
	{
		printf("%d\n",ans[i]);
	}	
}