P1197 [JSOI2008]星球大战

Link

题解

将“摧毁”看成“修建”，反向离线并查集处理。

代码

#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#include <stack>
#include <string>
#include <vector>
#define pii pair<int, int>
#define mpr make_pair
const int maxn = 400000 + 10;
using namespace std;

vector<int>G[maxn];
int fa[maxn], vis[maxn];

void init(int n) {
    for (int i = 0; i < n; i++)fa[i] = i;
}

int findr(int x) {
    if (x == fa[x])return x;
    else return fa[x] = findr(fa[x]);
}

void merge(int x, int y) {
    int xr = findr(x), yr = findr(y);
    if (xr != yr)fa[xr] = yr;
}

int main() {
    stack<int>o;
    vector<int>ans;
    vector<pii>edges;
    int n, m, x, y, k;
    cin >> n >> m;
    init(n);
    while (m--) {
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
        edges.push_back(mpr(x, y));
    }
    cin >> k;
    int tot = n - k;
    while (k--) {
        cin >> x;
        o.push(x);
        vis[x] = 1;
    }
    for (auto e : edges) {
        int u = e.first, v = e.second;
        if (!vis[u] && !vis[v] && findr(u) != findr(v)) {
            merge(u, v);
            tot--;
        }
    }
    ans.push_back(tot);
    while(!o.empty()) {
        int i = o.top(); o.pop();
        vis[i] = 0;
        tot++;
        for (auto j : G[i]) {
            if (!vis[j] && findr(i) != findr(j)) {
                tot--;
                merge(i, j);
            }
        }
        ans.push_back(tot);
    }
    reverse(ans.begin(), ans.end());
    for (auto i : ans)cout << i << endl;
    return 0;
}