zyHelloworld123 @ 2024-06-09 17:00:29
//"第一张图":通过邻接表存储边相连信息
//"第二张图":通过并查集逆向修建星球,复原计算连通数(计算方法是通过遍历边)
#include <bits/stdc++.h>
using namespace std;
const int N = 400040;
int head[N]; //邻接表头数组
struct edge{ //邻接表的节点
int from, to, next;
}edges[N];
int n, m, tot, k, cnt;
int p[N];
int is_crash[N]; //是否被摧毁
int crash[N]; //被摧毁的星球
int ans[N];
int find(int x){
if(p[x] != x)
p[x] = find(p[x]);
return p[x];
}
void merge(int x, int y){
p[find(x)] = find(y);
}
void addedge(int x, int y){
edges[++tot].from = x;
edges[tot].to = y;
edges[tot].next = head[x];
head[x] = tot; //head[x]存储所有以x为起始点的边序号,用next依次遍历
}
int main(void){
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i++)
p[i] = i;
//"第一张图",存储所有的边的互联信息
while(m--){
int x, y;
scanf("%d%d", &x, &y);
addedge(x, y);
addedge(y, x); //注意无向图两次插入
}
//记录所有摧毁信息
scanf("%d", &k);
for(int i = 0; i < k; i++){
scanf("%d", &crash[i]);
is_crash[crash[i]] = 1;
}
cnt = n - k;
//"第二张图",从并查集角度复原连通块
//从最后被摧毁后开始判断此时还有几个连通块,方法是通过遍历"第一张图"的所有边信息(边数组)
for(int i = 1; i <= 2 * m; i++){
int u = edges[i].from;
int v = edges[i].to;
if(!is_crash[u] && !is_crash[v] && find(u) != find(v)){
cnt--;
merge(u, v);
}
}
ans[k] = cnt;
//依次逆向复原,通过遍历当前轮次被摧毁的点的连接的边求解连通块个数(邻接表头)
for(int i = k - 1; i >= 0; i--){
is_crash[crash[i]] = 0;
cnt++;
for(int j = head[crash[i]]; j; j = edges[j].next){
int u = edges[j].from;
int v = edges[j].to;
if(!is_crash[v] && find(u) != find(v)){
cnt--;
merge(u, v);
}
}
ans[i] = cnt;
}
for(int i = 0; i <= k; i++)
printf("%d\n", ans[i]);
return 0;
}
by ChampionCyan @ 2024-06-26 17:32:40
没有
by zyHelloworld123 @ 2024-09-06 17:33:17
@ChampionCyan 你好,请问是没有错误的意思吗