记录编号	230485	评测结果	AAAAAAAAAA
题目名称	[JSOI 2008]星球大战starwar	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	1.454 s
提交时间	2016-02-22 09:59:39	内存使用	7.04 MiB

#include<cstdio>
int rank[400050];
int ufs[400050];
bool reach[400050];
int find(int x){
//	printf("%d",x);
	if(x!=ufs[x])ufs[x]=find(ufs[x]);
	return ufs[x];
}
void link(int a,int b){
//	printf("start");
	ufs[find(a)]=find(b);
}
struct edge{
	int to;
	int next;
}lst[400050];
int first[400050];
int len = 1;
void insert(int a,int b){
	lst[len].to = b;
	lst[len].next = first[a];
	first[a]=len++;
}
int damage[400050];
bool d[400050];
int count(int n){
	int tot=0;
	for(int i = 0;i<n;++i){
//		printf("start");
		if(!d[i]&&i==find(i))tot++;
	}
	return tot;
}
int s[400050];int top=0;
int read(){
	int x;char ch;
	while(ch=getchar(),ch>'9'||ch<'0');
	x=ch-48;
	while(ch=getchar(),ch<='9'&&ch>='0')x=(x<<3)+(x<<1)+ch-48;
	return x;
}
int main(){
	freopen("bzoj_1015.in","r",stdin);
	freopen("bzoj_1015.out","w",stdout);
	//逆序处理和输出，让时光倒流
	int n,m;
	n=read();m=read();
	int a,b;
	for(int i = 0;i<n;++i){
		rank[i]=1;
		ufs[i]=i;
	}
	for(int i = 0;i<m;++i){
		a=read();b=read();
		insert(a,b);
		insert(b,a);
	}
	int k;
	k=read();
	for(int i = 0;i<k;++i){
		damage[i]=read();
		d[damage[i]]=true;
	}
	for(int i = 0;i<n;++i){
		if(d[i])continue;
		for(int pt = first[i];pt;pt=lst[pt].next){
			if(d[lst[pt].to])continue;
			link(i,lst[pt].to);
		}
	}
	int tot=count(n);
	s[top++]=tot;
	bool flag;int pt;
	for(int i=k-1;i>=0;--i){
		d[damage[i]]=false;
		flag=reach[damage[i]];
		for(pt=first[damage[i]];pt;pt=lst[pt].next){
			if(!d[lst[pt].to]){
				link(damage[i],lst[pt].to);
				reach[damage[i]]=true;
				reach[lst[pt].to]=true;
				break;
			}
		}
		if(!flag&&!reach[damage[i]])tot++;
		for(;pt;pt=lst[pt].next){
			if(d[lst[pt].to])continue;
			if(find(damage[i])!=find(lst[pt].to)){
				link(damage[i],lst[pt].to);
				tot--;
				
			}
		}
		s[top++]=tot;
	}
	for(int i=top-1;i>=0;--i){
		printf("%d\n",s[i]);
	}
	fclose(stdin);fclose(stdout);
	return 0;
}