题目大意
给出N个星球之间的M个
连接关系，按顺序摧毁k个
星球，问每次摧毁后图中有
多少个连通块。
数据范围
1<=M<=200,000
1<=k<=N<=2M
1 /*思想： 反向恢复星球， 用并查集维护关系*/ 2 #include<cstdio> 3 using namespace std; 4 #define MAX 400000+99 5 #define MAXN 800000+99//不用在意范围，博主为了赶时间AC，没算 6 7 int fa[MAX]; 8 int n,m,k,tot; 9 int cmd[MAX],ans[MAX],vis[MAXN]; 10 int head[MAXN], cnt; 11 struct edge{ 12 int x,y; 13 int next; 14 }e[MAX]; 15 16 void add_edge(int x, int y) { 17 e[++cnt].x = x; 18 e[cnt].y = y; 19 e[cnt].next = head[x]; 20 head[x] = cnt; 21 } 22 23 int find(int x) { 24 if(fa[x] == x) return fa[x]; 25 else return fa[x] = find(fa[x]); 26 } 27 28 int main() { 29 scanf("%d%d",&n,&m); 30 for(int i = 0; i < n; i++) fa[i] = i; 31 int x,y,fax, fay; 32 for(int i = 1; i <= m; i++){ 33 scanf("%d %d", &x, &y); 34 add_edge(x,y); 35 add_edge(y,x); 36 } 37 scanf("%d", &k); 38 tot = n - k;//打击完后还剩的点 39 for(int i = 1; i <= k; i++) scanf("%d", &cmd[i]), vis[ cmd[i] ] = 1; 40 //记录并保存摧毁目标 （将他们每个都看成个联通快 41 for(int i = 1; i <= m*2; i++) {//合并没有打击到的 42 x = e[i].x , y = e[i].y ; 43 fax = find(x), fay = find(y); 44 if(!vis[x] && !vis[y])//如果都没打击到(体现倒推 45 if(fax != fay) {//并且没有连接过 46 fa[fax] = fay; 47 tot--;//将他们连接 ，联通快-- 48 } 49 } 50 ans[k+1] = tot;//此处为k次打击完了之后的ans 51 for(int j = k; j >= 1; j--) { // 我们的思想 52 x = cmd[j]; 53 vis[x] = 0;//恢复这个星球（倒推 54 tot++;//因为恢复了，所以多了一个点 55 for(int i = head[x]; i; i = e[i].next ) {//遍历与这个恢复星球相连的星球 56 y = e[i].y ; 57 fax = find(x), fay = find(y); 58 if(!vis[y] && fax != fay) {// 如果y没有被打击，而且没有相连过(即在另一个联通快 59 tot--;//合并 60 fa[fax] = fay;//注意尽量不要到过来赋值，这样会不断改变father 61 } 62 } 63 ans[j] = tot; 64 } 65 66 for(int i = 1; i <= k+1; i++) printf("%d ", ans[i]); 67 return 0; 68 }