BZOJ 1015 [JSOI2008] 星球大戰：逆向並查集動態維護連通塊數

BZOJ 1015 [JSOI2008] 星球大戰：逆向並查集動態維護連通塊數

給定無向圖 N 點 M 邊，初始所有點存活。依次摧毀 Q 個點（每次摧毀一個），求每次摧毀後的連通塊數（被摧毀點不計入連通塊）。N, M, Q ≤ 2×10^5。

核心技巧：時間逆向 + 並查集增量構建

1. 讀入所有邊與摧毀序列 destroy[1..Q]；
2. 標記所有被摧毀點 destroyed[x] = true；
3. 初始狀態：僅保留未被摧毀的點及其邊，構建並查集，連通塊數 now = N - Q；
4. 逆向處理：從 Q 遞減到 1，「恢復」點 x = destroy[i]：
   • destroyed[x] = false，now++（新增孤立點）；
   • 遍歷 x 的所有鄰邊，若鄰居未被摧毀，Unite(x, neighbor)，合併成功 now--；
   • 記錄當前 now 為第 i-1 次摧毀後的答案（即第 i 次摧毀前的狀態）。
5. 最後按正序輸出答案。

關鍵代碼

#include <bits/stdc++.h>
using namespace std;
const int MAXM = 400400;

struct Edge { int to, next; } e[MAXM];
int head[MAXM], tot;
int fa[MAXM], stk[MAXM], destroy[MAXM], top, now;
bool destroyed[MAXM];

int Find(int x) { return fa[x] == x ? x : fa[x] = Find(fa[x]); }

void Unite(int x, int y) {
    int fx = Find(x), fy = Find(y);
    if (fx == fy) return;
    --now; fa[fy] = fx;
}

void AddEdge(int x, int y) {
    e[++tot] = {y, head[x]}; head[x] = tot;
    e[++tot] = {x, head[y]}; head[y] = tot;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, m; cin >> n >> m;
    for (int i = 0, u, v; i < m; ++i) {
        cin >> u >> v; ++u; ++v;          // 1-based
        AddEdge(u, v);
    }
    int q; cin >> q;
    for (int i = 1; i <= q; ++i) {
        cin >> destroy[i]; ++destroy[i];
        destroyed[destroy[i]] = true;
    }

    now = n - q;
    for (int i = 1; i <= n; ++i) if (!destroyed[i])
        for (int j = head[i]; j; j = e[j].next)
            if (!destroyed[e[j].to]) Unite(i, e[j].to);

    stk[++top] = now;                     // 所有摧毀完成後的狀態
    for (int i = q; i >= 1; --i) {
        int x = destroy[i];
        destroyed[x] = false;
        ++now;                            // 恢復孤立點
        for (int j = head[x]; j; j = e[j].next)
            if (!destroyed[e[j].to]) Unite(x, e[j].to);
        stk[++top] = now;
    }
    while (top) cout << stk[top--] << '\n';
    return 0;
}

關鍵細節

• 點編號輸入從 0 起，代碼統一 ++u 轉 1-based，避免 0 索引混淆；
• now 初始為 存活點數（N-Q），每次 Unite 成功遞減；
• 恢復點時先 ++now 再合併邊，邏輯清晰；
• 答案棧 stk 逆序存儲，最後彈出正序輸出；
• 並查集無按秩合併也可通過（路徑壓縮已足夠），若 TLE 可加 rank 或 size 優化。

複雜度

• 時間：O((N+M+Q) α(N))，近似線性；
• 空間：O(N+M+Q)。

經典變體

• 邊刪除/添加動態連通性 → 同樣逆向 + 並查集；
• 帶權連通塊（如最大點權和） → 並查集維護 sum[fa]；
• 查詢兩點是否連通 → 逆向過程中記錄 Find(u)==Find(v) 時刻。

「逆向思維 + 並查集增量構建」是處理「刪除操作難、添加操作易」動態圖問題的萬金油模板，必須熟練掌握。