洛谷P1197 星球大战【并查集】

题目：https://www.luogu.org/problemnew/show/P1197

题意：有n个结点m条无向边，k次操作每次摧毁一个结点并询问此时有多少连通块。

思路：平时在线的搞多了都没想到这道题完全可以存下结果之后输出。

对于那些要被摧毁的城市，我们只需要先都摧毁，然后倒序的进行恢复。就可以求出每一次操作的结果了。

因为对于摧毁我们不好用并查集，但是对于重建就比较好用并查集了。

所以分成两步，把所有没有被摧毁的连通的结点都合并起来。

然后按照倒序加入被摧毁的结点，将他和他所邻接的结点进行合并。

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<map>
  4 #include<set>
  5 #include<cstring>
  6 #include<algorithm>
  7 #include<vector>
  8 #include<cmath> 
  9 #include<stack>
 10 #include<queue>
 11 #include<iostream>
 12 
 13 #define inf 0x7fffffff
 14 using namespace std;
 15 typedef long long LL;
 16 typedef pair<string, string> 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<int>sss;
 56 stack<int>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
", ans.top());
103         ans.pop();
104     }
105     
106     return 0; 
107 }