BZOJ 1015 星球大戰

逆序并查集

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
using namespace std;
const int maxn = 1000000 + 10;
vector<int>G[maxn];
int f[maxn];
int Bo[maxn];
int List[maxn];
int ans[maxn];
int n,m;
int find(int x)
{
	return f[x] == x ? x : f[x] = find(f[x]);
}
int bfs(int u)
{
	int res = 0;
	int sz = G[u].size();
	for(int i=0;i<sz;i++)
	{
		if(Bo[G[u][i]]) continue;
		int x = find(u);
		int y = find(G[u][i]);
		if(x != y)
		{
			f[y] = x;
			res++;
		}
	}
	return res;
}
int main()
{
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		int u , v;
		for(int i=0;i<=n;i++)
		{
			f[i] = i;
			G[i].clear();
		}
		memset(ans,0,sizeof(ans));
		memset(List,0,sizeof(List));
		memset(Bo,0,sizeof(Bo));
		for(int i=1;i<=m;i++)
		{
			scanf("%d%d",&u,&v);
			u++;v++;
			G[u].push_back(v);
			G[v].push_back(u);
		}
		int k;
		scanf("%d",&k);
		for(int i=1;i<=k;i++)
		{
			scanf("%d",&List[i]);
			Bo[++List[i]] = 1;
		}
		for(int i=1;i<=n;i++)
			if(!Bo[i]) bfs(i);
		for(int i=1;i<=n;i++)
			if(f[i] == i) ans[k]++;
		ans[k] -= k;
		for(int i=k;i;i--)
		{
			int x = List[i];
			Bo[x] = 0;
			ans[i-1] = ans[i] - bfs(x) + 1;
		}
		for(int i=0;i<=k;i++)
			printf("%d\n",ans[i]);
	}
	return 0;
}