P1197 [JSOI2008] 星球大战

题目

P1197 [JSOI2008] 星球大战

算法标签: 并查集, 反向考虑, 枚举

思路

按题目描述, 给定一个图, 每次删除一个点, 求联通块的数量, 直接求的算法时间复杂度太高, 无法通过, 考虑反向添加点, 假设当前图$G$是已经全部删除目标点的剩余图, 假设当前联通块的数量是$k$, 然后倒序添加点, 如果合并两个新的连通块, 那么$k-1$, 因为是从后向前添加点, 因此记录答案也是逆序记录的, 最后再逆序输出即可

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

const int N = 4e5 + 10, M = N;

int n, m, k;
int head[N], ed[M], ne[M], idx;
int del[N];
int fa[N];
bool vis[N] = {
   0};
vector<int> ans;

void add(int u, int v) {
   
    ed[idx] = v, ne[idx] = head[u], head[u] = idx++;
}

int find(int u) {
   
    if (u != fa[u]) fa[u] = find(fa[u]);
    return fa[u];
}

void merge(int u, int v) {
   
    int fa1 = find(u), fa2 = find(v);
    if (fa1 != fa2) fa[fa2] = fa1;
}

int main() {
   
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    memset(head, -1, sizeof head);

    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
   
        int u, v;
        cin >> u >> v;
        add(u, v), add(v, u);
    }
    for (int i = 0; i <= n; ++i) fa[i] = i;

    cin >> k;
    for (int i = 0; i < k; ++i) {
   
        cin >> del[i];
        vis[del[i]] = true;
    }

    // 计算初始连通性
    int cnt = n - k;
    for (int i = 0; i < idx; ++i) {
   
        int u = ed[i];
        int v = ed[i ^ 1];
        if (!vis[u] && !vis[v] && find(u) != find(v)) {
   
            merge(u, v);
            cnt--;
        }
    }
    ans.push_back(cnt);
    
    for (int i = k - 1; i >= 0; --i) {
   
        int u = del[i];
        vis[u] = false;
        cnt++;

        for (int j = head[u]; ~j; j = ne[j]) {
   
            int v = ed[j];
            if (!vis[v] && find(u) != find(v)) {
   
                cnt--;
                merge(u, v);
            }
        }
        ans.push_back(cnt);
    }
    
    reverse(ans.begin(), ans.end());
    for (int val : ans) cout << val << "\n";

    return 0;
}