题意
给出一个 \(n\) 个点，\(m\) 条边的无向图，对其进行 \(k\) 次操作，每次操作会删除一个当前无向图中存在的点及其相邻的边，求原图 和每次操作之后的图的连通块个数
sol
由于需要计算连通块个数，可以自然的想到使用并查集解决。然而，删除某个点后，我们无法通过并查集快速地得知其与其他点是否直接联通，也就无法快速地计算。
考虑按照操作的逆序来计算，那么就相当于在一个 \(n-k\) 个点的无向图中，每次操作添加一个点，并添加一些与其相邻的边，求原图和每次操作之后的图的连通块个数。这样，就可以通过并查集来解决这个问题了。
代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_map>
#include <vector>#define x first
#define y second using namespace std;
typedef pair<int, int> PII;const int N = 400005;int n, m, k;
int g[N];
PII edges[N];
unordered_map<int, int> depth;
vector<PII> edge[N];
int fa[N];
int ans[N];int find(int x){if (fa[x] == x) return x;return fa[x] = find(fa[x]);
}int main(){scanf("%d%d", &n, &m);for (int i = 1; i <= m; i ++ ) {int x, y;scanf("%d%d", &x, &y);edges[i] = {x, y};}scanf("%d", &k);for (int i = 1; i <= k; i ++ ) {scanf("%d", &g[i]);depth[g[i]] = k - i + 1;}for (int i = 1; i <= m; i ++ ) {int dx = depth[edges[i].x], dy = depth[edges[i].y];edge[max(dx, dy)].push_back(edges[i]);}for (int i = 1; i <= n; i ++ ) fa[i] = i;int cnt = n - k;for (int d = 0; d <= k; d ++ , cnt ++ ){// printf("#depth: %d\n", d);for (auto e : edge[d]){// printf("%d %d\n", e.x, e.y);int fx = find(e.x), fy = find(e.y);if (fx == fy) continue;cnt -- ;fa[fx] = fy;}ans[d] = cnt;}for (int i = k; i >= 0; i -- ) printf("%d\n", ans[i]);return 0;
}
