求助:RE4个点

P1197 [JSOI2008] 星球大战

can_can_need_ @ 2023-11-08 21:39:03

#include <bits/stdc++.h>
using namespace std;
#define umap unordered_map
#define forn_(i, l, r) for (int i = l; i >= r; i--)
#define forn(i, l, r) for (int i = l; i <= r; i++)
const int N = 4e5 + 5;

vector<int> g[N];
int n, m, k;
int u, v, x[N];
bool is[N];
int cnt, ans[N];
class DSU {
public:
    void init(int n) {
        size = n;
        p.resize(size + 1);
        forn(i, 0, size - 1) p[i] = i;
    }
    int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    bool merge(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx == fy) return 0;
        p[fx] = fy;
        cnt--;
        return 1;
    }

private:
    vector<int> p;
    int size;
} p;
void dfs(int now) {
    forn(i, 0, g[now].size() - 1) {
        int v = g[now][i];
        if (is[v]) continue;
        if (!p.merge(now, v)) continue;
        dfs(v);
    }
}
int main() {
    cin >> n >> m;
    forn(i, 1, m) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    cin >> k;
    forn(i, 1, k) cin >> x[i], is[x[i]] = 1;

    p.init(n);
    cnt = n - k;
    forn(i, 0, n - 1) {
        if (is[i]) continue;
        dfs(i);
    }
    ans[k + 1] = cnt;
    forn_(i, k, 1) {
        is[x[i]] = 0;
        cnt++;
        dfs(x[i]);
        ans[i] = cnt;
    }

    forn(i, 1, k + 1) cout << ans[i] << endl;
    return 0;
}

N开1e6还是RE


|