题目传送门(BZOJ)
>原文链接<

题解 :

这是一个常见套路 : 反向询问,变分为合的使用并查集.

我们把询问反向过来, 一开始把所有不是以K个询问为端点的边连接起来, 并且$ans[k]=n-k$

对于每个询问打掉的点, 我们连好它之后那个询问的所有边, 并同时使用并查集维护联通块数量

对于一条边, 若它的两个端点已经在同一个集合里, 跳过它

若它的另一个端点是在这个点之前被消灭的, 跳过它

否则连接, 并且当前联通块数量又少了一个.

这样做$k$次(从$k-1\to 0$), 把记录好的答案输出即可.

代码 :

代码是好久之前写的, 不是很清真

#include <cstdio>#include <iostream>#include <algorithm>#include <queue>using namespace std;const int N = 410000;int fa[N<<1];int a[N];int head[N], cnt;int ans[N];int to[N], nxt[N];void add(int x, int y) { to[++cnt] = y; nxt[cnt] = head[x] ; head[x] = cnt;}int find(int x) { return x==fa[x] ? x : fa[x] = find(fa[x]);}bool hav[N<<1];int main() { int n, m, k; scanf("%d%d", &n, &m); for(int i=1;i<=n;i++) fa[i] = i; for(int i=1;i<=m;i++) { int x, y; scanf("%d%d", &x, &y); x++, y++; add(x, y); add(y, x); } for(int i=1;i<=n;i++) hav[i]=1; scanf("%d", &k); ans[k]=n-k; for(int i=1;i<=k;i++) { scanf("%d", &a[i]); a[i]++; hav[a[i]]=0; } for(int i=1;i<=n;i++) { if(!hav[i]) continue; for(int j=head[i];j;j=nxt[j]) { if(!hav[to[j]]) continue; int dx=find(i), dy = find(to[j]); if(dx!=dy) fa[dx] = dy, ans[k]--; } } hav[a[k]]=1; for(int i=k-1;i>=0;i--) { int x = a[i+1]; ans[i] = ans[i+1]+1; for(int j=head[x];j;j=nxt[j]) { int t = to[j]; if(!hav[t]) continue; int dy = find(t), dx = find(x); if(dx!=dy) { fa[dy] = dx; ans[i] --; } } hav[a[i]]=1; } for(int i=0;i<=k;i++) { printf("%d\n", ans[i]); }}