[JSOI2008]星球大战

Description

BZOJ1015

Solution

并差集经典应用。反向模拟，删点变加点，并差集维护联通块。

Code

 #include <cstdio>

const int N = 4e5+10;

int hd[N], nxt[N], to[N], cnt;
int fa[N];
int vis[N], a[N], ans[N];

inline void adde(int x, int y) {
	cnt++;
	nxt[cnt] = hd[x];
	to[cnt] = y;
	hd[x] = cnt;
}

int find(int x) {
	return x == fa[x] ? x : fa[x] = find(fa[x]);
}

bool merge(int x, int y) {
	int fx = find(x), fy = find(y);
	if (fx == fy) return false;
	fa[fx] = fy;
	return true;
}

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 1, x, y; i <= m; ++i) {
		scanf("%d%d", &x, &y);
		x++, y++;
		adde(x, y);
		adde(y, x);
	}
	for (int i = 1; i <= n; ++i) fa[i] = i;
	int k, cnt = n;
	scanf("%d", &k);
	for (int i = 1; i <= k; ++i) scanf("%d", &a[i]), vis[++a[i]] = 1, cnt--;
	for (int i = 1; i <= n; ++i) if (!vis[i]) {
		for (int j = hd[i]; j; j = nxt[j]) if (!vis[to[j]]) {
			if (merge(i, to[j])) cnt--;
		}
	}
	ans[k+1] = cnt;
	for (int i = k; i; --i) {
		cnt++;
		vis[a[i]] = 0;	
		for (int j = hd[a[i]]; j; j = nxt[j]) if (!vis[to[j]]) {
			if (merge(a[i], to[j])) cnt--;
		}
		ans[i] = cnt;
	}
	for (int i = 1; i <= k+1; ++i) {
		printf("%d
", ans[i]);
	}
	return 0;
}