【玄关】求调

P1197 [JSOI2008] 星球大战

_KMnO4_ @ 2024-01-04 18:36:20

2个点AC,剩下的WA

#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 4e5 + 10;
bool vis[maxn];
vector<int> G[maxn];
int n, m, k, x, y, ans, a[maxn], ht[maxn], fa[maxn];
int findRt(int x) {
    if (x == fa[x]) return x;
    return fa[x] = findRt(fa[x]);
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 1; i <= m; i++) {
        scanf("%d %d", &x, &y);
        x++, y++;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    scanf("%d", &k);
    ans = n - k;
    for (int i = 1; i <= k; i++) {
        scanf("%d", ht + i);
        ht[i]++;
        vis[ht[i]] = true;
    }
    for (int i = 1; i <= n; i++) {
        x = findRt(i);
        for (auto v : G[i]) {
            y = findRt(v);
            if (x == y || vis[v] || vis[i]) continue;
            fa[x] = y;
            ans--;
        }
    }
    a[k + 1] = ans;
    for (int i = k; i; i--) {
        ans++;
        x = findRt(ht[i]);
        vis[ht[i]] = false;
        for (auto v : G[ht[i]]) {
            y = findRt(v);
            if (vis[v] || x == y) continue;
            ans--;
            fa[x] = y;
        }
        a[i] = ans;
    }
    for (int i = 1; i <= k + 1; i++) printf("%d\n", a[i] < 1 ? 1 : a[i]);
    return 0;
}

|