p1197星球大戰

*Problem:p1197星球大戰

*State:ac

*Algorithm:逆序，并查集

/*
*Problem:P1197星球大戰 
*State:ac
*Algorithm:逆序，并查集 
*/
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio> 
using namespace std;
const int maxn=400005;
const int maxm=200005;
int pre[maxn],liantong[maxn],cuihui[maxn];
bool destruct[maxn];
int n,m,x,y,k,total;
struct edge{
	int x,y;
}a[maxm];
vector<int> citycon[maxn];
int find(int root)
{
	return root==pre[root]?root:pre[root]=find(pre[root]);
}
void join(int root1,int root2)
{
	int x,y;
	if((x=find(root1))!=(y=find(root2)))
	{
		pre[x]=y;
		total--;
	}
}
int main(void)
{
	memset(destruct,false,sizeof(destruct));
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
    {
    	pre[i]=i;
	}
	for(int i=0;i<m;i++)
	{
		scanf("%d%d",&x,&y);
		a[i].x=x;a[i].y=y;
		citycon[x].push_back(y);
		citycon[y].push_back(x);
	}
	scanf("%d",&k);
	total=n-k;
	for(int i=0;i<k;i++)
	{
		scanf("%d",&cuihui[i]);
		destruct[cuihui[i]]=true; 
	}
	for(int i=0;i<m;i++)
	{
		if(!destruct[a[i].x]&&!destruct[a[i].y])
		{
			join(a[i].x,a[i].y);
		} 
	}
	liantong[k]=total;
	for(int i=k-1;i>=0;i--)
	{
		total++;
		destruct[cuihui[i]]=false;
		for(int j=0;j<citycon[cuihui[i]].size();j++)
		{
			if(!destruct[citycon[cuihui[i]][j]])
			join(cuihui[i],citycon[cuihui[i]][j]);
		}
		liantong[i]=total;
	}
	for(int i=0;i<=k;i++)
	{
		printf("%d\n",liantong[i]);
	}
	return 0;
}