[题目链接]
https://www.lydsy.com/JudgeOnline/problem.php?id=1015
[算法]
考虑离线 ， 将删点转化为加点 ， 用并查集维护连通性即可
时间复杂度 : O(NlogN)
[代码]
#include<bits/stdc++.h> using namespace std; #define MAXN 400010 #define MAXM 200010 struct edge { int to,nxt; } e[MAXM << 1]; int n,m,cnt,tot,k; int a[MAXN],ans[MAXN],head[MAXN],atk[MAXN],fa[MAXN]; bool alive[MAXN]; template <typename T> inline void read(T &x) { T f = 1; x = 0; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0'; x *= f; } inline void addedge(int u,int v) { tot++; e[tot] = (edge){v,head[u]}; head[u] = tot; } inline int get_root(int x) { if (fa[x] == x) return x; return fa[x] = get_root(fa[x]); } inline void merge(int x,int y) { int u = get_root(x) , v = get_root(y); fa[u] = v; } int main() { read(n); read(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++; addedge(x,y); addedge(y,x); } memset(alive,true,sizeof(alive)); scanf("%d",&k); for (int i = 1; i <= k; i++) { scanf("%d",&atk[i]); alive[++atk[i]] = false; } for (int u = 1; u <= n; u++) { for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; if (alive[u] && alive[v]) merge(u,v); } } for (int i = 1; i <= n; i++) { if (alive[i] && get_root(i) == i) cnt++; } ans[k + 1] = cnt; for (int i = k; i >= 1; i--) { alive[atk[i]] = true; cnt++; for (int x = head[atk[i]]; x; x = e[x].nxt) { int v = e[x].to; if (alive[v] && get_root(atk[i]) != get_root(v)) { merge(atk[i],v); cnt--; } } ans[i] = cnt; } for (int i = 1; i <= k + 1; i++) printf("%d\n",ans[i]); return 0; }