P1197 [JSOI2008]星球大战 40分 求助

原题

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <stack>
#include <vector>

using namespace std;

const int maxn = 4e5 + 10;

int n, m, k;
int fa[maxn];
bool in[maxn];
vector<int> G[maxn];
stack<int> f, ans;
int finds(int x) {
    if(fa[x] != x)return fa[x] = finds(fa[x]);
    return x;
}

int main () {

    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++) fa[i] = i;
    for(int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    scanf("%d", &k);
    for(int i = 1; i <= k; i++) {
        int id;
        scanf("%d", &id);
        f.push(id);
        in[id] = 1;
    }
    int now = n - k;
    for(int i = 0; i < n; i++) {
        if(in[i])continue;
        int len = G[i].size();
        for(int j = 0; j < len; j++) {
            if(G[i][j])continue;
            int fx = finds(i), fy = finds(G[i][j]);
            if(fx != fy) {
                now--;
                fa[fx] = fy;
            }
        }
    }
    ans.push(now);
    while(k--) {
        int top = f.top(), len = G[top].size();
        f.pop();
        for(int i = 0; i < len; i++) {
            int city = G[top][i];
            if(in[city])continue;
            int v = finds(city), u = finds(top);
//          printf("%d %d\n", u, v);
            if(u != v) {
                fa[u] = v;
                now--;
            }
        } 
        if(in[top])now++;
        in[top] = 0;
        ans.push(now);
    }
    while(!ans.empty()) {
        printf("%d\n", ans.top());
        ans.pop();
    }
    return 0;
}```