BZOJ传送门

每次删边显然十分复杂，所谓正难则反（= = 数学思路？）

只要把摧毁的建筑倒着加入并查集就行了

每次合并，连通块就会减1，但总的连通块要减去那些还未加入的星球（= = 貌似说不清楚）

直接上代码。

#include <cstdio>
#define maxm 200001
#define maxn 400001
int b[maxn],f[maxn],d[maxn],c[maxn],h[maxn],last[maxn],head[maxn],l;

void add(int x,int y)
{
	l++;
	h[l] = y;
	last[l] = head[x];
	head[x] = l;
}

int find(int x)
{
	if (f[x] == x) return x;
	return f[x] = find(f[x]);
}

void read(int &i)
{
	char x;
	for (x = getchar();x < '0';x = getchar());
	for (i = 0;x >= '0';x = getchar()) i = i * 10 + x - '0';
}

int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for (int i = 1;i <= m;i++)
	{
		int x,y;
		read(x);read(y);
		add(++x,++y);
		add(y,x);
	}
	int q;
	read(q);
	for (int i = 1;i <= n;i++)
		b[i] = 1,f[i] = i;
	for (int i = 1;i <= q;i++)
	{
		read(d[i]);
		b[++d[i]] = 0;
	}
	int t = q;\\t就是还没加入的星球个数
	int sum = n;
	for (int i = 1;i <= n;i++)
		if (b[i] == 1)
		{
			for (int x = head[i];x;x = last[x])
				if (b[h[x]] == 1)
				{
					int r1 = find(i),r2 = find(h[x]);
					if (r1 != r2)
					{
						f[r1] = r2;
						sum--;
					}
				}
		}
	
	for (int i = q;i >= 1;i--)
	{
		c[i] = sum - t;
		b[d[i]] = 1;
		for (int x = head[d[i]];x;x = last[x])
			if (b[h[x]] == 1)
			{
				int r1 = find(d[i]),r2 = find(h[x]);
					if (r1 != r2)
					{
						f[r1] = r2;
						sum--;
					}
			}
		t--;
	}
	printf("%d\n",sum-t);
	for (int i = 1;i <= q;i++)
		printf("%d\n",c[i]);
	return 0;
}