T2 P1197 [JSOI2008] 星球大战
传送门：洛谷P1197
很好的一道并查集题，每一颗星球之间都通过一条隧道组成一个连通块，我们可以用并查集来维护两个点之间的连通性，但是这个题里面它要求删除一个点，似乎我们以前做过的所有的并查集题里面都没有涉及到删点这个东西，既然不能删点，那我们就不删，反过来想想，我们把它删掉的每一个点给加上，这样操作起来就方便的多；
具体实现过程：
先将所有的边的情况记下来，在把所有要删的点记下来，我们先求删掉所有点后连通块的数量，再把删掉的点一个一个加上，对删掉的点相连的点遍历，通过并查集维护连通性；
不说多的，直接上代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e5 + 5;
int n, m, k, tot, head[maxn], del[maxn], f[maxn], fa[maxn], ans[maxn];
struct Edge {
int v, nxt;
} edge[maxn];
struct edge {
int u, v;
} e[maxn];
void add(int u, int v) {
edge[++ tot] = {v, head[u]};
head[u] = tot;
}
int Find(int x) {
if (x == fa[x]) return fa[x];
return fa[x] = Find(fa[x]);//记得路径压缩，不然要TLE
}
void read() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++ i)
fa[i] = i;
for (int i = 1; i <= m; ++ i) {
scanf("%d%d", &e[i].u, &e[i].v);
add(e[i].u + 1, e[i].v + 1);
add(e[i].v + 1, e[i].u + 1);
e[i].u ++, e[i].v ++;
}
scanf("%d", &k);
tot = n - k;
for (int i = 1; i <= k; ++ i) {
scanf("%d", &del[i]);
del[i] ++;
f[del[i]] = 1;
}
for (int i = 1; i <= m; ++ i) {
int u = e[i].u, v = e[i].v;
if (f[u] || f[v]) continue ;//如果当前点删掉的，就不加；
int fu = Find(fa[u]), fv = Find(fa[v]);
if (fu != fv) {
tot --;
fa[fu] = fv;
}
}
ans[k + 1] = tot;//注意！！ k + 1;
for (int i = k; i >= 1; -- i) {
tot ++;//加上一个点，加上一个连通块；
int u = del[i];
f[u] = 0;
for (int i = head[u]; i; i = edge[i].nxt) {
int v = edge[i].v;
if (f[v]) continue ;
int fv = Find(fa[v]), fu = Find(fa[u]);
if (fv != fu) {
tot --;
fa[fv] = fu;
}
}
ans[i] = tot;
}
for (int i = 1; i <= k + 1; ++ i) {//要输出 k + 1 个！！
printf("%d\n", ans[i]);
}
}
int main() {
read();
return 0;
}