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;
}