提交记录

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<vector>
#include<stack>
#define REG register
#define INL inline
#define Max(x,y) (x<y?y:x)
#define int long long
using namespace std;
int fa[2000005];int co[1000005];
INL int find(int x){
	if(fa[x]!=x)fa[x]=find(fa[x]);
	return fa[x];
}
INL int merge(int x,int y,int fl){
	int xx=find(x),yy=find(y);
	int re;
	if(xx == yy||fl)re=0;
	else re=1;
	if(xx!=yy)
	fa[xx]=yy;
	return re;
}
int n,m;
int x[1000005],y[1000005];
int visit[1000005];

vector<int> l[1000005];
int ed[1000005];

signed main(){
	cin>>n>>m;
	for(REG int i=0;i<n;i++)fa[i]=i,co[i]=1;
	for(REG int i=1;i<=m;i++){
		scanf("%lld%lld",&x[i],&y[i]);
		l[x[i]].push_back(i);
		l[y[i]].push_back(i);
	}
	int k;
	cin>>k;
	int cnt=n;
	for(int i=1;i<=k;i++){
		scanf("%lld",&ed[i]);
		co[ed[i]]=0;
		cnt--;
	}
	stack<int>sta;
	for(int i=0;i<n;i++){
		if(!co[i])continue;
		for(REG int j=0;j<l[i].size();j++){
			if(visit[l[i][j]])continue;
			if(co[x[l[i][j]]] == 0||co[y[l[i][j]]] == 0){
				continue;
			}
			merge(x[l[i][j]],y[l[i][j]],1);
		}
	}
	for(REG int i=k;i>=1;i--){
		sta.push(cnt);
		co[ed[i]]=1;
		int flag=1;
		int use=1;
		for(REG int j=0;j<l[ed[i]].size();j++){
			if(visit[l[ed[i]][j]])continue;
			if(x[l[ed[i]][j]]!=ed[i]&&co[x[l[ed[i]][j]]] == 0)continue;
			if(y[l[ed[i]][j]]!=ed[i]&&co[y[l[ed[i]][j]]] == 0)continue;
			visit[l[ed[i]][j]]=1;
			cnt-=merge(x[l[ed[i]][j]],y[l[ed[i]][j]],use);
			use=0;
			flag=0;
		}
		if(flag)cnt++;
	}
	sta.push(cnt);
	while(!sta.empty()){
		cout<<sta.top()<<endl;
		sta.pop();
	}
}