题目描述
很久以前,在一个遥远的星系,一个黑暗的帝国靠着它的超级武器统治者整个星系。
某一天,凭着一个偶然的机遇,一支反抗军摧毁了帝国的超级武器,并攻下了星系中几乎所有的星球。
这些星球通过特殊的以太隧道互相直接或间接地连接。
但好景不长,很快帝国又重新造出了他的超级武器。
凭借这超级武器的力量,帝国开始有计划地摧毁反抗军占领的星球。
由于星球的不断被摧毁,两个星球之间的通讯通道也开始不可靠起来。
现在,反抗军首领交给你一个任务:
给出原来两个星球之间的以太隧道连通情况以及帝国打击的星球顺序,以尽量快的速度求出每一次打击之后反抗军占据的星球的连通快的个数。(如果两个星球可以通过现存的以太通道直接或间接地连通,则这两个星球在同一个连通块中)。
输入格式
第一行包含两个整数,N 和 M,分别表示星球的数目和以太隧道的数目。星球用 0∼N−1 的整数编号。
接下来的 M 行,每行包括两个整数 x,y,表示星球 x 和星球 y 之间有“以太”隧道,可以直接通讯。
接下来的一行为一个整数 k,表示将遭受攻击的星球的数目。
接下来的 k 行,每行有一个整数,按照顺序列出了帝国军的攻击目标。这 k 个数互不相同,且都在 0 到 n−1 的范围内。
输出格式
第一行是开始时星球的连通块个数。
接下来的 k 行,每行一个整数,表示经过该次打击后现存星球的连通块个数。
算法1
(并查集) $O(M)$
逆向思维,把摧毁转换成 修建。
参考文献
推荐一发 我的分享
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 4 * 1e5 + 10; // 全局变量;
int res; // 储存答案;
int n, m, k;
// n 星球数目, m 以太隧道数目, k 遭受攻击的星球数目
int fa[N];
// 并查集
int h[N], s[N], e[N], ne[N], idx;
// 存图, e[] 存边到达的终点, s 存边的起点
bool st[N];
void add(int a, int b)
{
e[idx] = b, s[idx] = a, ne[idx] = h[a], h[a] = idx ++;
}
int find(int x) // 并查集, 找祖先 (路径压缩)
{
if (x == fa[x]) return x;
return fa[x] = find(fa[x]);
}
int main()
{
memset(h, -1, sizeof h); // 初始化表头
memset(st, true, sizeof st);// 初始时没有点被摧毁
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i ++ ) fa[i] = i;
for (int i = 1; i <= m; i ++ )
{
int x, y;
scanf("%d %d", &x, &y);
add(x, y), add(y, x); // 读入无向边
}
scanf("%d", &k); // 读入遭受攻击的星球数目
stack<int> pk, ans;
// 分别储存 pk 被攻击的星球, ans 输出答案
for (int i = 1; i <= k; i ++ )
{
int q;
scanf("%d", &q);
st[q] = false, pk.push(q);
// 标记为摧毁, 算法核心是将摧毁转换成 修建 , 所以逆时间顺序压入栈中
}
m = 2 * m, res = n - k;
// 无向边边数 * 2, res 储存连通块数量
for (int i = 1; i <= m; i ++ ) // 先找所有完好的边构成的连通块数量
{
int S = find(s[i]), E = find(e[i]);
// 先找到这条边的入点和出点
if(st[e[i]] && st[s[i]] && S != E) // 如果这两条边都没有被摧毁, 且不在同一个连通块中
{
res --; // 连通块的数量就可以减一了
fa[E] = S; // 加入同一个连通块
}
}
ans.push(res); // 逆时间的初始答案, k 个点都被摧毁 或 理解为没有新增的点
while(pk.size()) // 只要不为空
{
int tot = pk.top(); // 取出栈顶
pk.pop();
res ++; // 多了一个星球,连通块数量加一
st[tot] = true; // 当前星球已被修建
for (int i = h[tot]; i != -1; i = ne[i]) // 遍历这个点的所有出边
{
int j = e[i]; // 边的终点
int S = find(tot), E = find(e[i]); // 找到起点和终点的祖先
if (st[j] && S != E) // 终点没有被摧毁, 不是一个祖先也就是不在一个连通块中
{
res --; // 连通块数量减一
fa[E] = S; // 加入一个连通块
}
}
ans.push(res); // 压入当前修建好这个星球的答案
}
while (ans.size()) // 逆输出答案
{
res = ans.top();
ans.pop();
printf("%d\n", res);
}
return 0;
}
// 去掉注释正好一百行,开心(`・ω・´)
原因
将连通块断开的情况有很多,难以由单点出发维护,需要全局遍历 $O(n)$
但是连上连通块,恰好符合并查集的合并操作,$O(1)$ 可以完成
这思路真的秀