并查集 - [JSOI2008] 星球大战

题目描述

很久以前，在一个遥远的星系，一个黑暗的帝国靠着它的超级武器统治着整个星系。某一天，凭着一个偶然的机遇，一支反抗军摧毁了帝国的超级武器，并攻下了星系中几乎所有的星球。这些星球通过特殊的以太隧道互相直接或间接地连接。

但好景不长，很快帝国又重新造出了他的超级武器。凭借这超级武器的力量，帝国开始有计划地摧毁反抗军占领的星球。由于星球的不断被摧毁，两个星球之间的通讯通道也开始不可靠起来。

现在，反抗军首领交给你一个任务：给出原来两个星球之间的以太隧道连通情况以及帝国打击的星球顺序，以尽量快的速度求出每一次打击之后，反抗军占据的星球的连通块的个数。

注：如果两个星球可以通过现存的以太通道直接或间接地连通，则这两个星球在同一个连通块中。

输入格式

1. 第一行包含两个整数 n 和 m，分别表示星球的数目和以太隧道的数目。星球用 0 到 n-1 的整数编号。
2. 接下来的 m 行，每行包括两个整数 x 和 y，表示星球 x 和星球 y 之间存在一条双向的“以太”隧道。
3. 接下来的一行为一个整数 k，表示帝国计划打击的星球个数。
4. 接下来的 k 行，每行有一个整数，按照顺序列出了帝国军的攻击目标。这 k 个数互不相同，且都在 0 到 n-1 的范围内。

输出格式

输出文件共 k+1 行。

• 第一行是开始时（打击发生前）星球的连通块个数。
• 接下来的 k 行，每行一个整数，表示经过该次打击后，现存星球的连通块个数。

🌍 样例数据

输入

8 13
0 1
1 6
6 5
5 0
0 6
1 2
2 3
3 4
4 5
7 1
7 2
7 6
3 6
5
1
6
3
5
7

输出

1
1
1
2
3
3

解题思路

1. 逆向思维：

   • 正序：删除节点 → 难以维护
   • 逆序：从最终状态开始，逐步添加被删除的节点 → 并查集擅长处理添加

2. 算法步骤：

   • 先用邻接表（链式前向星）存储所有边
   • 记录所有会被删除的节点，并标记
   • 建立最终状态（所有删除操作完成后）的并查集：
     • 初始连通块数 = 剩余节点数
     • 连接所有未被删除的节点之间的边，每成功合并一次，连通块数减1
   • 逆序处理删除操作：
     • 恢复一个被删除的节点（标记取消）
     • 连通块数+1（新增一个独立点）
     • 尝试连接该节点与其所有未被删除的邻居，每成功合并一次，连通块数减1
     • 记录当前连通块数
   • 正序输出记录的结果

代码实现

#include <iostream>
using namespace std;const int MAXN = 400005;    // 节点数上限
const int MAXM = 800005;    // 边数上限（双向边）int n, m, k;                // n:节点数 m:边数 k:删除操作数
int head[MAXN], nxt[MAXM], v[MAXM];  // 链式前向星存图
int c[MAXN], flg[MAXN];     // c:删除顺序 flg:标记节点是否被删除
int Fa[MAXN], Ans[MAXN];    // Fa:并查集 Ans:答案数组// 并查集查找（路径压缩）
int GetFa(int x) {if (x == Fa[x]) return x;return Fa[x] = GetFa(Fa[x]);
}int main() {// 输入节点数和边数scanf("%d%d", &n, &m);// 建图（链式前向星，双向边）int L = 0;for (int i = 1; i <= m; i++) {int x, y;scanf("%d%d", &x, &y);x++; y++;  // 转为1-based，方便处理// x -> yL++; v[L] = y; nxt[L] = head[x]; head[x] = L;// y -> xL++; v[L] = x; nxt[L] = head[y]; head[y] = L;}// 输入删除操作scanf("%d", &k);for (int i = 1; i <= k; i++) {int x; scanf("%d", &x);c[i] = x + 1;        // 记录被删除的节点flg[c[i]] = 1;        // 标记为已删除}// 初始化并查集for (int i = 1; i <= n; i++) Fa[i] = i;// 建立最终状态（所有删除操作完成后）int cnt = n - k;  // 初始连通块数 = 剩余节点数for (int i = 1; i <= n; i++) {if (flg[i]) continue;           // 跳过已删除的节点int fi = GetFa(i);                // 先找到当前节点的根for (int p = head[i]; p; p = nxt[p]) {int j = v[p];if (flg[j]) continue;         // 跳过已删除的邻居int fj = GetFa(j);if (fi != fj) {                // 不在同一集合，合并Fa[fj] = fi;cnt--;                      // 连通块数减1}}}Ans[k + 1] = cnt;  // 记录最后一次删除后的结果// 逆序恢复被删除的节点for (int j = k; j >= 1; j--) {int u = c[j];      // 当前要恢复的节点flg[u] = 0;         // 取消删除标记cnt++;              // 新增一个独立点，连通块数+1int fu = GetFa(u);   // 找到当前节点的根for (int p = head[u]; p; p = nxt[p]) {int x = v[p];if (flg[x]) continue;      // 邻居还未恢复，跳过int fx = GetFa(x);if (fu != fx) {              // 不在同一集合，合并Fa[fx] = fu;cnt--;                    // 连通块数减1}}Ans[j] = cnt;  // 记录恢复该节点后的结果}// 输出答案for (int j = 1; j <= k + 1; j++)  printf("%d\n", Ans[j]);return 0;
}

关键点解释

1. 空间设置：

   • MAXN = 400005：节点数最大为 400000
   • MAXM = 800005：边数最大为 200000，双向边需要 400000，再加一些余量

2. 链式前向星：

   • head[i]：节点 i 的第一条边的编号
   • nxt[p]：编号为 p 的边的下一条边
   • v[p]：编号为 p 的边指向的节点
   • 这种存图方式比 vector 更快，空间利用率高

3. 并查集优化：

   • 路径压缩：return Fa[x] = GetFa(Fa[x])
   • 提前计算根节点：避免在循环中重复调用 GetFa

4. 连通块计数：

   • 初始：n - k（所有未删除的节点各自独立）
   • 合并：cnt--（两个集合合并为一个）
   • 恢复节点：cnt++（新增一个独立点）

5. 逆向处理：

   • 先建立最终状态
   • 从最后一次删除往前处理
   • 每次恢复一个节点，尝试合并

时间复杂度

• 建图：O(m)
• 并查集操作：O((n+m) × α(n))，α(n) 为阿克曼函数的反函数，近似常数
• 总复杂度：O(n + m + k)，可以轻松通过本题

注意事项

1. 节点编号从 0 开始，内部处理转为 1-based 更方便
2. 边要存双向，否则图会不连通
3. 在合并时要注意先找到根再比较，避免重复查找
4. 输出顺序：第一行是初始状态，后面依次是每次删除后的状态