把删点操作倒序变成加点操作，用并查集动态维护当前剩余图的连通块数量。
OJ: luogu
题目 ID: P1197
难度:普及+/提高
标签:并查集逆序处理图论连通块
日期: 2026-06-22 21:28
题意
给定一个无向图，点编号为 0..n-1。接着给出若干个点的摧毁顺序。
需要输出初始图的连通块数量，以及每次摧毁一个点后剩余图的连通块数量。
思路
先看一个可以直接验证想法的朴素解：
cpp
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 55;
int n, m, k;
vector<int> graph_edges[MAXN];
int destroy_order[MAXN];
bool alive[MAXN], vis[MAXN];
int count_components() {
memset(vis, false, sizeof(vis));
int cnt = 0;
for (int i = 0; i < n; i++) {
if (!alive[i] || vis[i]) {
continue;
}
cnt++;
queue<int> q;
q.push(i);
vis[i] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int j = 0; j < (int)graph_edges[u].size(); j++) {
int v = graph_edges[u][j];
if (alive[v] && !vis[v]) {
vis[v] = true;
q.push(v);
}
}
}
}
return cnt;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
graph_edges[u].push_back(v);
graph_edges[v].push_back(u);
}
cin >> k;
for (int i = 1; i <= k; i++) {
cin >> destroy_order[i];
}
for (int i = 0; i < n; i++) {
alive[i] = true;
}
cout << count_components() << '\n';
for (int i = 1; i <= k; i++) {
alive[destroy_order[i]] = false;
cout << count_components() << '\n';
}
return 0;
}暴力做法是每次删除一个点后重新 BFS 统计连通块。这样太慢。
并查集擅长合并，不擅长删除。所以把操作倒过来：
- 正向是依次删点；
- 逆向就是从最终剩余图开始，按相反顺序把点加回来。
恢复一个点 u 时：
- 它自己先形成一个新连通块；
- 检查所有邻点
v； - 如果
v已经存在，就用并查集合并； - 每次成功合并，连通块数量减一。
逆向每一步的图，正好对应正向某次删除后的剩余图。因此记录逆向答案，再按正序输出即可。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 400005;
const int MAXM = 200005;
struct Edge {
int u;
int v;
};
int n, m, k;
Edge edges[MAXM];
vector<int> graph_edges[MAXN];
int destroy_order[MAXN];
bool destroyed[MAXN], active_node[MAXN];
int fa[MAXN], sz[MAXN];
int answer[MAXN];
int components;
void init_dsu() {
for (int i = 0; i < n; i++) {
fa[i] = i;
sz[i] = 1;
}
}
int find_set(int x) {
while (fa[x] != x) {
fa[x] = fa[fa[x]];
x = fa[x];
}
return x;
}
void unite_set(int x, int y) {
int fx = find_set(x);
int fy = find_set(y);
if (fx == fy) {
return;
}
if (sz[fx] < sz[fy]) {
swap(fx, fy);
}
fa[fy] = fx;
sz[fx] += sz[fy];
components--;
}
void add_planet(int u) {
active_node[u] = true;
components++;
for (int i = 0; i < (int)graph_edges[u].size(); i++) {
int v = graph_edges[u][i];
if (active_node[v]) {
unite_set(u, v);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> edges[i].u >> edges[i].v;
graph_edges[edges[i].u].push_back(edges[i].v);
graph_edges[edges[i].v].push_back(edges[i].u);
}
cin >> k;
for (int i = 1; i <= k; i++) {
cin >> destroy_order[i];
destroyed[destroy_order[i]] = true;
}
init_dsu();
components = 0;
for (int i = 0; i < n; i++) {
if (!destroyed[i]) {
add_planet(i);
}
}
answer[k + 1] = components;
for (int i = k; i >= 1; i--) {
add_planet(destroy_order[i]);
answer[i] = components;
}
for (int i = 1; i <= k + 1; i++) {
cout << answer[i] << '\n';
}
return 0;
}复杂度
每个点恢复一次，每条边被检查常数次。
总时间复杂度为：
text
O(n + m)空间复杂度为
总结
动态图删点问题常用技巧是倒序处理。
把删除变成添加后，就可以用并查集维护连通块数量。