Description
题库链接
给你一张 \(n\) 点， \(m\) 条边的无向图，每次摧毁一个点，问你剩下几个联通块。
\(1\leq n\leq 2m,1\leq m\leq 200000\)
Solution
删点不好操作，我们考虑倒序，变为加点。加边时，只考虑没删除的点间的连边，并查集维护。
是一道喜闻乐见的大水题。
Code
//It is made by Awson on 2018.2.27#include <bits/stdc++.h>#define LL long long#define dob complex<double>#define Abs(a) ((a) < 0 ? (-(a)) : (a))#define Max(a, b) ((a) > (b) ? (a) : (b))#define Min(a, b) ((a) < (b) ? (a) : (b))#define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))#define writeln(x) (write(x), putchar('\n'))#define lowbit(x) ((x)&(-(x)))using namespace std;const int N = 400000;void read(int &x) { ???char ch; bool flag = 0; ???for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || 1); ch = getchar()); ???for (x = 0; isdigit(ch); x = (x<<1)+(x<<3)+ch-48, ch = getchar()); ???x *= 1-2*flag;}void print(int x) {if (x > 9) print(x/10); putchar(x%10+48); }void write(int x) {if (x < 0) putchar('-'); print(Abs(x)); }int n, m, u, v, t, a[N+5], ans[N+5], flag[N+5];struct tt {int to, next, cost; }edge[(N<<2)+5];int path[N+5], top, cnt, fa[N+5];void add(int u, int v) {edge[++top].to = v, edge[top].next = path[u], path[u] = top; }int find(int o) {return fa[o] ? fa[o] = find(fa[o]) : o; }void work() { ???read(n), read(m); cnt = n; ???for (int i = 1; i <= m; i++) { ???read(u), read(v); ++u, ++v; add(u, v), add(v, u); ???} ???read(t); for (int i = 1; i <= t; i++) read(a[i]), ++a[i], flag[a[i]] = 1; cnt -= t; ???for (int u = 1; u <= n; u++) ???if (flag[u] == 0) ???????for (int j = path[u]; j; j = edge[j].next) { ???????if (flag[edge[j].to] == 1) continue; ???????if (find(u)^find(edge[j].to)) fa[find(u)] = find(edge[j].to), --cnt; ???????} ???ans[t+1] = cnt; ???for (int i = t; i >= 1; i--) { ???flag[a[i]] = 0; int u = a[i]; ++cnt; ???for (int j = path[u]; j; j = edge[j].next) ???????if (flag[edge[j].to] == 0) ???????if (find(u)^find(edge[j].to)) fa[find(u)] = find(edge[j].to), --cnt; ???ans[i] = cnt; ???} ???for (int i = 1; i <= t+1; i++) writeln(ans[i]);}int main() { ???work(); return 0;}