上海百度推广,百度网站优化是什么意思,学校网站源码php,semester什么意思目录 题目算法标签: 并查集, 反向考虑, 枚举思路代码 题目
P1197 [JSOI2008] 星球大战
算法标签: 并查集, 反向考虑, 枚举
思路
按题目描述, 给定一个图, 每次删除一个点, 求联通块的数量, 直接求的算法时间复杂度太高, 无法通过, 考虑反向添加点, 假设当前图 G G G是已经全… 目录 题目算法标签: 并查集, 反向考虑, 枚举思路代码 题目
P1197 [JSOI2008] 星球大战
算法标签: 并查集, 反向考虑, 枚举
思路
按题目描述, 给定一个图, 每次删除一个点, 求联通块的数量, 直接求的算法时间复杂度太高, 无法通过, 考虑反向添加点, 假设当前图 G G G是已经全部删除目标点的剩余图, 假设当前联通块的数量是 k k k, 然后倒序添加点, 如果合并两个新的连通块, 那么 k − 1 k-1 k−1, 因为是从后向前添加点, 因此记录答案也是逆序记录的, 最后再逆序输出即可
代码
#include iostream
#include algorithm
#include cstring
#include vectorusing 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};
vectorint 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;
}
