Bzoj 1015(并查集+离线逆向思维)

Bzoj 1015
连通性问题可以用并查集做。不要总想着tarjan什么的。。况且tarjan也是有向图的

这题并查集正着做很麻烦,因为并查集并不支持删除,只支持添加。
所以我们先把所有询问存下来离线,先把不会删的点先加上,之后再从最后开始一直加点(加了的点之间的连边也是要连的),然后每次询问统计答案即可,这里统计答案不要用$O(n)$的算法,用一个$tot$来维护答案值。

刚开始做的时候忘记加过的点标记了。。。而且输出6行我输出5行认为对了。。其实还要输出一开始图的连通分量。。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 400000 + 5;
int k, n, m, f[MAXN], tot, vi[MAXN], ans[MAXN], p[MAXN];
vector<int> G[MAXN];
int find(int x) {return f[x] == x ? x : f[x] = find(f[x]);}
void addEdge(int u) {
for (int i=0;i<G[u].size();i++) {
int v = G[u][i];
if (!vi[v]) continue;
int x = find(u), y = find(v);
if (x != y) tot--, f[x] = y;
}
}
void clean() {
for (int i=0;i<=n;i++) G[i].clear(), f[i] = i, vi[i] = true;
}
void solve() {
clean();
for (int i=1;i<=m;i++) {
int x, y;
scanf("%d%d", &x, &y);
G[x].push_back(y), G[y].push_back(x);
}
scanf("%d", &k), tot = n - k;
for (int i=1;i<=k;i++) {
scanf("%d", &p[i]);
vi[p[i]] = false;
}
int kase = k + 1;
for (int i=1;i<=n;i++) if (vi[i]) addEdge(i);
ans[kase--] = tot;
for (int i=k;i>=1;i--) {
tot++, addEdge(p[i]), vi[p[i]] = true;
ans[kase--] = tot;
}
for (int i=1;i<=k+1;i++) printf("%d\n", ans[i]);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
scanf("%d%d", &n, &m), solve();
return 0;
}

------ 本文结束 ------