P1197 星球大战
网页链接
P1197 星球大战
题目描述
很久以前，在一个遥远的星系，一个黑暗的帝国靠着它的超级武器统治着整个星系。
某一天，凭着一个偶然的机遇，一支反抗军摧毁了帝国的超级武器，并攻下了星系中几乎所有的星球。这些星球通过特殊的以太隧道互相直接或间接地连接。
但好景不长，很快帝国又重新造出了他的超级武器。凭借这超级武器的力量，帝国开始有计划地摧毁反抗军占领的星球。由于星球的不断被摧毁，两个星球之间的通讯通道也开始不可靠起来。
现在，反抗军首领交给你一个任务：给出原来两个星球之间的以太隧道连通情况以及帝国打击的星球顺序，以尽量快的速度求出每一次打击之后反抗军占据的星球的连通块的个数。（如果两个星球可以通过现存的以太通道直接或间接地连通，则这两个星球在同一个连通块中）。
输入格式
输入文件第一行包含两个整数n , m n,mn,m，分别表示星球的数目和以太隧道的数目。星球用0 ∼ n − 1 0 \sim n-10∼n−1的整数编号。
接下来的m mm行，每行包括两个整数x , y x,yx,y，表示星球x xx和星球y yy之间有“以太”隧道，可以直接通讯。
接下来的一行为一个整数k kk，表示将遭受攻击的星球的数目。
接下来的k kk行，每行有一个整数，按照顺序列出了帝国军的攻击目标。这k kk个数互不相同，且都在0 00到n − 1 n-1n−1的范围内。
输出格式
第一行是开始时星球的连通块个数。接下来的k kk行，每行一个整数，表示经过该次打击后现存星球的连通块个数。
输入输出样例 #1
输入 #1
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 1 2 3 3说明/提示
【数据范围】
对于100 % 100\%100%的数据，1 ≤ m ≤ 2 × 10 5 1\le m \le 2\times 10^51≤m≤2×105，1 ≤ n ≤ 2 m 1\le n \le 2m1≤n≤2m，x ≠ y x \neq yx=y。
解题思路
本题是并查集 + 逆向思维的经典问题。正向思考时，每次摧毁一个星球会导致连通块数量增加，并需要重新计算连通性，操作复杂。逆向思考：从最终状态（所有被摧毁的星球都已消失）出发，逐步“恢复”被摧毁的星球，每次恢复时用并查集合并相邻的存活星球，即可高效维护连通块数量。最后将逆向得到的答案倒序输出，即得到每次打击后的连通块数。
1. 问题等价转化
- 有n nn个星球（编号0 ∼ n − 1 0 \sim n-10∼n−1）和m mm条双向隧道，构成无向图。
- 帝国按顺序摧毁k kk个星球，要求输出初始连通块数，以及每次摧毁后的连通块数。
- 正向删除节点难以用并查集维护（并查集只支持合并，不支持删除）。因此将过程反转：
- 先假设所有将被摧毁的星球都已经消失，只考虑剩下的n − k n-kn−k个星球，计算连通块数。这个状态对应第k kk次打击之后。
- 然后按摧毁顺序的逆序逐个“恢复”星球。每恢复一个星球，它先作为一个新的孤立连通块（连通块数 +1），然后遍历它的所有邻居，若邻居是存活的，则用并查集合并两者，每成功合并一次连通块数 -1。
- 记录每次恢复后的连通块数，最后连同初始状态一起倒序输出。
2. 算法实现
- 建图：使用邻接表存储无向边。读入n , m n, mn,m，然后读入m mm条边，双向添加。
- 标记被摧毁的星球：
- 读入k kk和摧毁顺序数组
a[1..k]。 - 用布尔数组
b[i]标记星球i ii是否被摧毁（初始全部为false，读入摧毁目标后置为true）。
- 读入k kk和摧毁顺序数组
- 初始化并查集：
fa[i] = i，每个星球自成一个集合。 - 计算最终状态的连通块数：
- 令
s = n - k（存活星球数量，初始视为每个存活星球独立，连通块数等于存活星球数）。 - 遍历所有未被摧毁的星球，对每个星球调用
df(i)进行合并。df(x)函数：遍历x xx的所有邻居，若邻居存活且与x xx不在同一集合，则合并，s--，并递归处理邻居（实际上递归可以省略，但这里用递归实现了类似 DFS 的合并，保证所有连通的存活节点都被合并）。由于每个节点只会被处理一次，复杂度可控。 - 将此时的
s存入答案数组c[k+1]（表示第k kk次打击后的连通块数）。
- 令
- 逆序恢复星球：
- 对于i = k i = ki=k递减到1 11：
- 将
b[a[i]]置为false（恢复该星球）。 s++（新增一个孤立星球）。- 调用
df(a[i])，将其与所有存活的邻居合并，合并时s--。 - 将更新后的
s存入c[i]（表示第i − 1 i-1i−1次打击后的连通块数；特别地，c[1]对应初始状态）。
- 将
- 对于i = k i = ki=k递减到1 11：
- 输出答案：按顺序输出
c[1]到c[k+1]，即初始状态和第1 ∼ k 1 \sim k1∼k次打击后的连通块数。
3. 复杂度分析
- 时间复杂度：建图O ( m ) O(m)O(m)；初始化并查集O ( n ) O(n)O(n)；第一次合并存活节点时，每个节点和每条边最多被访问一次，并查集操作近似O ( α ( n ) ) O(\alpha(n))O(α(n))；逆序恢复k kk个节点，每次同样遍历其邻接边，总边数仍为O ( m ) O(m)O(m)。因此总时间复杂度O ( n + m + k α ( n ) ) O(n + m + k \alpha(n))O(n+m+kα(n))，其中α \alphaα是阿克曼函数的反函数，可视为常数。n ≤ 2 m ≤ 4 × 10 5 n \le 2m \le 4\times 10^5n≤2m≤4×105，完全可行。
- 空间复杂度：邻接表O ( n + m ) O(n + m)O(n+m)，并查集和标记数组O ( n ) O(n)O(n)，答案数组O ( k ) O(k)O(k)，总空间O ( n + m ) O(n + m)O(n+m)，满足限制。
总结
通过逆向操作，将“删除节点”转化为“添加节点”，并利用并查集动态维护连通块数量。每次添加节点时，先增加一个连通块，再与所有已存在的邻居合并，每合并一次连通块数减一。最终倒序输出即可得到所有询问的答案。该方法巧妙避免了正向删除的困难，是处理动态连通性问题的常用技巧。
代码简要说明
- 全局数组：
g[N]：邻接表，存储每个星球的邻居。a[N]：按顺序存储被摧毁的星球编号。b[N]：布尔标记，true表示该星球已被摧毁。fa[N]：并查集的父节点数组。c[N]：答案数组，c[i]存储第i − 1 i-1i−1次打击后的连通块数（c[1]为初始状态）。
ad()函数：读入一条边并双向加入邻接表。ini()函数：初始化并查集，每个节点父节点指向自己。fd(x)函数：并查集查找，带路径压缩。df(x)函数：从节点x xx出发，遍历其所有邻居，若邻居存活且不在同一集合，则合并，连通块数s--，并递归处理邻居。该函数用于将x xx所在的连通分量完全合并。- 主函数：
- 读入n , m n, mn,m，建图。
- 读入k kk和摧毁序列，标记
b[a[i]] = true。 - 初始化并查集，
s = n - k。 - 遍历所有未被摧毁的节点，调用
df(i)合并连通块。 c[k+1] = s。- 逆序恢复：
for i = k down to 1：b[a[i]] = false; s++; df(a[i]); c[i] = s;。 - 按顺序输出
c[1]到c[k+1]。
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=400005;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;ll n,m,k;ll a[N],b[N],c[N],s;vector<ll>g[N];ll fa[N];voidad(){ll e,u;cin>>e>>u;g[e].push_back(u);g[u].push_back(e);}voidini(){for(ll i=0;i<n;i++)fa[i]=i;}llfd(ll x){returnfa[x]==x?x:(fa[x]=fd(fa[x]));}voiddf(ll x){for(ll i=0;i<(ll)g[x].size();i++){if(b[g[x][i]])continue;ll fx=fd(x),fy=fd(g[x][i]);if(fx==fy)continue;fa[fx]=fy;s--;df(g[x][i]);}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n>>m;while(m--)ad();cin>>k;for(ll i=1;i<=k;i++){cin>>a[i];b[a[i]]=1;}ini();s=n-k;for(ll i=0;i<n;i++){if(b[i])continue;df(i);}c[k+1]=s;for(ll i=k;i>=1;i--){b[a[i]]=0;s++;df(a[i]);c[i]=s;}for(ll i=1;i<=k+1;i++)printf("%lld\n",c[i]);return0;}
