本文共 2132 字，大约阅读时间需要 7 分钟。
题目：
题意：有n个结点m条无向边，k次操作每次摧毁一个结点并询问此时有多少连通块。
思路：平时在线的搞多了都没想到这道题完全可以存下结果之后输出。
对于那些要被摧毁的城市，我们只需要先都摧毁，然后倒序的进行恢复。就可以求出每一次操作的结果了。
因为对于摧毁我们不好用并查集，但是对于重建就比较好用并查集了。
所以分成两步，把所有没有被摧毁的连通的结点都合并起来。
然后按照倒序加入被摧毁的结点，将他和他所邻接的结点进行合并。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 13 #define inf 0x7fffffff 14 using namespace std; 15 typedef long long LL; 16 typedef pair pr; 17 18 int n, m, k; 19 const int maxn = 4e5 + 5; 20 int par[maxn]; 21 int head[maxn]; 22 struct edge{ 23 int u, v, nxt; 24 }e[maxn]; 25 int tot = 0; 26 bool destroy[maxn]; 27 28 void addedge(int u, int v) 29 { 30 e[tot].u = u; 31 e[tot].v = v; 32 e[tot].nxt = head[u]; 33 head[u] = tot++; 34 e[tot].u = v; 35 e[tot].v = u; 36 e[tot].nxt = head[v]; 37 head[v] = tot++; 38 } 39 40 int ffind(int x) 41 { 42 if(par[x] == x)return x; 43 else return par[x] = ffind(par[x]); 44 } 45 46 void init() 47 { 48 for(int i = 0; i < n; i++){ 49 par[i] = i; 50 head[i] = -1; 51 destroy[i] = false; 52 } 53 } 54 55 stack sss; 56 stack ans; 57 int main() 58 { 59 scanf("%d%d", &n, &m); 60 init(); 61 for(int i = 0; i < m; i++){ 62 int u, v; 63 scanf("%d%d", &u, &v); 64 addedge(u, v); 65 } 66 scanf("%d", &k); 67 for(int i = 0; i < k; i++){ 68 int d; 69 scanf("%d", &d); 70 destroy[d] = true; 71 sss.push(d); 72 } 73 74 int cnt = n - k; 75 for(int i = 0; i < tot; i++){ 76 if(!destroy[e[i].u] && !destroy[e[i].v]){ 77 int fu = ffind(e[i].u), fv = ffind(e[i].v); 78 if(fu != fv){ 79 cnt--; 80 par[fu] = fv; 81 } 82 } 83 } 84 ans.push(cnt); 85 while(!sss.empty()){ 86 int x = sss.top();sss.pop(); 87 cnt++; 88 destroy[x] = false; 89 for(int i = head[x]; i != -1; i = e[i].nxt){ 90 if(!destroy[e[i].u] && !destroy[e[i].v]){ 91 int fu = ffind(e[i].u), fv = ffind(e[i].v); 92 if(fu != fv){ 93 cnt--; 94 par[fu] = fv; 95 } 96 } 97 } 98 ans.push(cnt); 99 }100 101 while(!ans.empty()){102 printf("%d\n", ans.top());103 ans.pop();104 }105 106 return 0; 107 }
转载于:https://www.cnblogs.com/wyboooo/p/11039488.html