有大佬帮忙看看这个错误在哪吗,目前40分

P1197 [JSOI2008] 星球大战

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 你好,请问是没有错误的意思吗


|