嗯...

 

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

 

这道题是并查集，但思路比较奇葩...

 

首先初始化，然后把读入的x，y存成一个无向图，接着把摧毁的星球打上标记。

然后枚举，看相邻的两个星球是否都没被摧毁，如果都没被摧毁并且两个的祖先不同，那么把它们合并成一个连通块，连通块个数减一。

 

下面是这道题的鬼畜之处：

倒叙枚举，把摧毁的一个星球修复，连通块个数加一。然后每连一条边，将这两个点合并，连通块个数减一。

 

AC代码：

1 #include
      
        2 #include
       
         3  4 using namespace std; 5  6 const int maxn = 400010; 7  8 int k, m, n, tot; 9 int head[maxn], ans[maxn], broken[maxn], f[maxn];10 bool flag[maxn];11 12 struct node{13     int next, to, from;14 } h[maxn];15 16 inline void add(int u, int v){17     h[++tot].from = u;18     h[tot].next = head[u];19     head[u] = tot;20     h[tot].to = v;21 }22 23 inline int find(int x){24     if(f[x] != x) f[x] = find(f[x]);25     return f[x];26 }27 28 inline void unionn(int u, int v){29     u = find(u), v = find(v);30     if(u != v) f[v] = u;31 }32 33 int main(){34     scanf("%d%d", &n, &m);35     for(int i = 0; i <= n; i++){36         f[i] = i;37         head[i] = -1;38     }//初始化 39     for(int i = 1; i <= m; i++){40         int x, y;41         scanf("%d%d", &x, &y);42         add(x, y);43         add(y, x);44     }//储存图 45     scanf("%d", &k);46     for(int i = 1; i <= k; i++){47         scanf("%d", &broken[i]);48         flag[broken[i]] = 1;49     }50     int sum = n - k;//初始化所有点都是单独存在的 51     for(int i = 1; i <= 2 * m; i++){52         if(!flag[h[i].from] && !flag[h[i].to] && find(h[i].from) != find(h[i].to)){
    //要是起点、终点都没毁坏，并且他们没有连通 53             sum--;//连一条边 减一个连通块 54             unionn(h[i].from, h[i].to);55         }56     }57     ans[k + 1] = sum;58     for(int i = k; i >= 1; i--){59         sum++;60         flag[broken[i]] = 0;//修复，连通块+1 61         for(int j = head[broken[i]]; j != -1; j = h[j].next){62             if(!flag[h[j].to] && find(broken[i]) != find(h[j].to)){
    //枚举子点 63                 sum--;//连一边减一个 64                 unionn(broken[i], h[j].to);65             }66         }67         ans[i] = sum;68     }69     for(int i = 1; i <= k + 1; i++)70         printf("%d\n", ans[i]);71     return 0;72 }