[bzoj1015][JSOI2008]星球大战——并查集+离线处理

时间:2024-07-05 11:33:08

题解

给定一张图,支持删点和询问连通块个数

按操作顺序处理的话要在删除点的同时维护图的形态(即图具体的连边情况),这是几乎不可做的

我们发现,这道题可以先读入操作,把没删的点的边先连上,然后再倒序处理操作

这样的话从删点变成了加点,而且只要维护连通块的数量,用并查集可以快速的解决这个问题

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 4 * 200000;
int n, m, q[maxn];
vector<int> G[maxn];
int fa[maxn], added[maxn], des[maxn], ans[maxn];
int tot = 0;
int find(int x) { return fa[x] = fa[x] == x ? x : find(fa[x]); }
void add(int x) {
int p = find(x), q;
added[x] = 1;
for (int i = 0; i < G[x].size(); i++) {
if (added[G[x][i]]) {
q = find(G[x][i]);
if (p != q) {
fa[q] = p;
tot--; //连通块少一个
}
}
}
}
int main() {
// freopen("input", "r", stdin);
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i++) {
int x, y;
scanf("%d %d", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
memset(added, 0, sizeof(added));
for (int i = 0; i < n; i++)
fa[i] = i;
int d;
scanf("%d", &d);
for (int i = 1; i <= d; i++) {
scanf("%d", &q[i]);
des[q[i]] = 1;
}
for (int i = 0; i < n; i++) {
if (!des[i]) {
tot++;
add(i);
added[i] = 1;
}
}
ans[d + 1] = tot;
for (int i = d; i > 0; i--) {
tot++; //连通块多一个
add(q[i]);
added[q[i]] = 1;
ans[i] = tot;
}
for (int i = 1; i <= d + 1; i++)
printf("%d\n", ans[i]);
return 0;
}