样例没过,求调

P1197 [JSOI2008] 星球大战

Rhss @ 2023-05-19 13:38:53

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
const int N = 4e5 + 10, M = 2e5 + 10;
int n, m, k;
int h[N], e[M], ne[M], idx;
int f[N], broke[N], ans[N], id[N];
pll edg[M];
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int find(int x) {
    if (x == f[x]) return x;
    return f[x] = find(f[x]);
}
int main() {
    scanf("%d%d", &n, &m);
    memset(h , -1 , sizeof h);
    for (int i = 0 ; i < n ; ++i) f[i] = i;
    for (int i = 1 ; i <= m ; ++i) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
        edg[i] = {a, b};
    }
    scanf("%d", &k);
    for (int i = 1 ; i <= k ; ++i) {
        int x;
        scanf("%d", &x);
        id[i] = x;
        broke[x] = 1;
    }
    int total = n - k;
    for (int i = 1 ; i <= m ; ++i) {
        int x = edg[i].x, y = edg[i].y;
        //如果起点和终点都没有被破坏 , 且不在一个集合内
        if (!broke[x] && !broke[y] && f[x] != f[y]) {
            //合并 , 联通块减少
            total--;
            //合并集合
            f[find(x)] = find(y);
        }
    }
    //K个地区都被占领后的联通块数量
    ans[k] = total;
    for (int i = k - 1 ; i >= 0 ; --i) {
        total++;
        //取出第 i 次会被占领的地区
        int t = id[i];
        broke[t] = 0;
        for (int j = h[j] ; ~j ; j = ne[j]) {
            int u = e[j];
            if (!broke[t] && !broke[u] && f[t] != f[u]) {
                total--;    
                f[find(t)] = find(u);
            }
        }
        ans[i] = total;
    }
    cout << endl;
    for (int i = 0 ; i <= k ; ++i) cout << ans[i] << endl;
    return 0;
}

|