星球之间互相直接或间接地连接
帝国开始使用死星有计划地摧毁反抗军占领的星球
给出星球间隧道的连通情况，已经帝国打击的顺序
要求以尽量快的速度求出每一次打击之后反抗军占据的星球的联通快的个数（若两个星球，直接或间接的通过现存的通道连接，则视为在一个联通块
输入格式：
第一行两个整数n， m，分别表示星球的数目和隧道的数目
接下来M行，每行两个整数x, y，表示星球x和y之间相连
接下来一个整数k，表示将要被摧毁的星球的数目
接下来k行，每行一个整数，按照顺序列出了帝国军的攻击目标
输出格式：
第一行是开始时星球的联通块个数，接下来k行，每行一个整数，表示经过打击后现存星球的联通块的个数
样例输入
8 13
0 1
1 6
6 5
5 0
0 6
1 2
2 3
3 4
4 5
7 1
7 2
7 6
3 6
5
1
6
3
5
7
样例输出
1
1
1
2
3
3
我们首先可以想到的是，直接用dfs暴力求连通块会超
很好，那么我们就只有(大概？)一个选择了：并查集维护连通性的同时解决问题
我们发现，题目进行的是删点操作，懂我的意思吧，并查集的维护是合并操作，不是删除操作
然后我们感觉思路有些迷迷糊糊，总感觉要通了，但还是卡的
那就把思考方向换一下。
如果最初默认删掉所有要删的点，然后倒着把要删的点一个一个修回去
很好，求解的答案没有出现差错
最初我们先预求出删掉所有要删的点后，连通块的数量
然后一个一个地往回加点。知道吧所有点加齐
最初预求删完所有点后连通块的数量的同时，将点与点之间父子关系连好
然后修点时再将与要修的点直接相连的点合并在要修的点上，同时维护连通块的数量，记录答案
具体实现和思路代码体会
（保证简单易懂)
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn = 400086; 4 struct enkidu { 5 int y, nex, x; 6 }e[maxn]; 7 int lin[maxn], len = 0; 8 int aim[maxn];//表示要摧毁哪些星球 9 int n, m, k; 10 int fa[maxn], ans[maxn]; 11 int vis[maxn];//判断有没有被炸 12 13 inline int read() { 14 int x = 0, y = 1; 15 char ch = getchar(); 16 while(!isdigit(ch)) { 17 if(ch == '-') y = -1; 18 ch = getchar(); 19 } 20 while(isdigit(ch)) { 21 x = (x << 1) + (x << 3) +ch - '0'; 22 ch = getchar(); 23 } 24 return x * y; 25 } 26 27 inline void insert(int xx, int yy) { 28 e[++len].y = yy; 29 e[len].x = xx; 30 e[len].nex = lin[xx]; 31 lin[xx] = len; 32 } 33 34 int getfather(int x) { 35 if(x == fa[x]) return x; 36 return fa[x] = getfather(fa[x]); 37 } 38 39 int main() { 40 memset(lin, -1, sizeof(lin)); 41 n = read(), m = read(); 42 for(int i = 0; i < n; ++i) fa[i] = i; 43 for(int i = 1; i <= m; ++i) { 44 int x, y; 45 x = read(), y = read(); 46 insert(x, y); 47 insert(y, x); 48 } 49 k = read(); 50 int num = n - k;//k次打击后，还剩下点的数量 51 for(int i = 1; i <= k; ++i) { 52 int star; 53 star = read(); 54 vis[star] = 1; 55 aim[i] = star; 56 } 57 for(int i = 1; i <= 2 * m; ++i) { 58 int x = e[i].x, y = e[i].y; 59 if(!vis[x] && !vis[y]) { 60 int u = getfather(x); 61 int v = getfather(y); 62 if(u != v) {//计算打击了k次后的连通块数量 63 num--;//表示有一对没有搜过的点连通，连通块数量减一 64 fa[v] = fa[u]; 65 } 66 } 67 } 68 ans[k + 1] = num;//k次打击后剩的连通块数量 69 //cout << num << ' '; 70 for(int i = k; i >= 1; --i) { 71 num++; 72 int force = aim[i]; 73 vis[force] = 0; 74 //cout << num << ' '; 75 int u = getfather(force); 76 //cout << u << ' '; 77 for(int j = lin[force]; j != -1; j = e[j].nex) { 78 //cout << j << ' '; 79 int to = e[j].y; 80 if(!vis[to]) { 81 int v = getfather(to); 82 if(u != v) { 83 num--; 84 fa[v] = u; 85 } 86 } 87 } 88 ans[i] = num; 89 } 90 for(int i = 1; i <= k + 1; ++i) 91 cout << ans[i] << ' '; 92 return 0; 93 }