Description
很久以前，在一个遥远的星系，一个黑暗的帝国靠着它的超级武器统治者整个星系。
某一天，凭着一个偶然的机遇，一支反抗军摧毁了帝国的超级武器，并攻下了星系中几乎所有的星球。
这些星球通过特殊的以太隧道互相直接或间接地连接。 但好景不长，很快帝国又重新造出了他的超级
武器。凭借这超级武器的力量，帝国开始有计划地摧毁反抗军占领的星球。由于星球的不断被摧毁，
两个星球之间的通讯通道也开始不可靠起来。现在，反抗军首领交给你一个任务：给出原来两个星球
之间的以太隧道连通情况以及帝国打击的星球顺序，以尽量快的速度求出每一次打击之后反抗军占据
的星球的连通快的个数。
（如果两个星球可以通过现存的以太通道直接或间接地连通，则这两个星球在同一个连通块中）。
输入文件第一行包含两个整数，N (1 < = N < = 2M) 和M (1 < = M < = 200,000)，
分别表示星球的数目和以太隧道的数目。星球用 0 ~ N-1的整数编号。
接下来的M行，每行包括两个整数X, Y，其中（0 < = X <> Y 表示星球x和星球y之间有“以太”隧道，
可以直接通讯。接下来的一行为一个整数k，表示将遭受攻击的星球的数目。接下来的k行，每行有一个
整数，按照顺序列出了帝国军的攻击目标。这k个数互不相同，且都在0到n-1的范围内。
Output
输出文件的第一行是开始时星球的连通块个数。
接下来的N行，每行一个整数，表示经过该次打击后现存星球的连通块个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| 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
|
Sample Output
Solution
题目大意：每次删除一个点 询问连通块个数。
Key：离线+并查集
把删除操作翻转为插入操作，那么对于插入操作维护并查集不同根节点数量就可以了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| #include <cstdio>
#include <algorithm>
using namespace std;
int getint() {
int r = 0, k = 1; char c = getchar();
for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
return r * k;
}
int to[400005], next[400005], cnte = 1, h[400005], f[400005], n, m, hit[400005], ans[400005];
void ins(int x, int y) {
to[++cnte] = y;
next[cnte] = h[x];
h[x] = cnte;
}
bool vis[400005], used[400005];
int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); }
void DFS(int now, int rt) {
f[now] = rt; vis[now] = true;
for (int i = h[now]; i; i = next[i])
if (!vis[to[i]] && !used[to[i]])
DFS(to[i], rt);
}
int main() {
n = getint(); m = getint();
for (int i = 1; i <= m; ++i) {
int x = getint()+1, y = getint()+1;
ins(x, y); ins(y, x);
}
int k = getint();
for (int i = 1; i <= k; ++i) {
hit[i] = getint()+1;
used[hit[i]] = true;
}
int ltk = 0;
for (int i = 1; i <= n; ++i) if (!vis[i] && !used[i]) { DFS(i, i); ++ltk; }
for (int i = k; i; --i) {
ans[i] = ltk;
int now = hit[i];
used[now] = false;
++ltk; f[now] = now;
for (int i = h[now]; i; i = next[i]) {
if (used[to[i]]) continue;
int a = find(now), b = find(to[i]);
if (a != b) {
f[a] = b;
--ltk;
}
}
} ans[0] = ltk;
for (int i = 0; i <= k; ++i) printf("%d\n", ans[i]);
}
|