「Bzoj 1015」「JSOI2008」星球大战starwar (并查集+离线逆向思维)

发表于 | 分类于 | | + s

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

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

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

#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;
}
------ 本文结束 ------