记录编号	584619	评测结果	AAAAAAAAAA
题目名称	[JSOI 2008]星球大战starwar	最终得分	100
用户昵称	ムラサメ	是否通过	通过
代码语言	C++	运行时间	1.925 s
提交时间	2023-11-13 23:27:25	内存使用	13.56 MiB

#include<bits/stdc++.h>
using namespace std;
int n,m,k,ed=0;
int pl[400010],head[400010],att[400010],ans[400010];
bool attf[400010];
struct node{
	int from,next,to;
}edge[400010];
void ins(int u,int v){
	edge[++ed].from=u;
	edge[ed].next=head[u];
	edge[ed].to=v;
	head[u]=ed;
}
int gett(int x){
	if(x==pl[x]){
		return x;
	}
	return pl[x]=gett(pl[x]);
}
int main(){
	freopen("bzoj_1015.in","r",stdin);
	freopen("bzoj_1015.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		pl[i]=i;
	}
	int u,v;
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		ins(u,v);
		ins(v,u);
	}
	cin>>k;
	int cnt=n-k;
	for(int i=1;i<=k;i++){
		cin>>u;
		attf[u]=1;
		att[i]=u;
	}
	for(int i=1;i<=m*2;i++){
		if(attf[edge[i].from]==0&&attf[edge[i].to]==0){
			if(pl[gett(edge[i].from)]!=pl[gett(edge[i].to)]){
				cnt--;
				pl[gett(edge[i].from)]=pl[gett(edge[i].to)];
			}
		}
	}
	ans[k+1]=cnt;
	for(int i=k;i>=1;i--){
		u=att[i];
		cnt++;
		attf[u]=0;
		for(int j=head[u];j!=0;j=edge[j].next){
			if(attf[edge[j].to]==0&&pl[gett(u)]!=pl[gett(edge[j].to)]){
				cnt--;
				pl[gett(u)]=pl[gett(edge[j].to)];
			}
		}
		ans[i]=cnt;
	}
	for(int i=1;i<=k+1;i++){
		cout<<ans[i]<<endl;
	}
	return 0;
}