CSUOJ 1601 War：離線並查集動態維護連通塊數

題目大意

N (≤ 100,000) 個村莊，M (≤ 100,000) 條路。Q (≤ M) 條路按給定順序被摧毀。每摧毀一條後，輸出當前連通塊（駐軍區）數量。

核心技巧：逆向思維 + 離線並查集

• 正向刪除邊難維護連通塊（需動態連通性，複雜）。
• **逆向**：先刪掉所有 Q 條路，構建初始圖，求連通塊數。然後**按逆序加回**被刪除的路。每加一條路，若兩端點原屬不同連通塊，合併並使連通塊數 -1。記錄每步結果，最後逆序輸出即為正序答案。

算法流程

1. 讀入 N, M，存儲所有邊 edges[i] = (u, v)。
2. 讀入 Q 及摧毀順序 del[1..Q]，標記 isDel[edgeId] = true。
3. 初始化並查集，連通塊數 ans = N。
4. 遍歷所有邊，若 !isDel[i]，union(u, v)（合併時 ans--）。
5. 逆序 i = Q..1：
   res[i] = ans; // 記錄加回第 i 條路**前**的連通塊數（即正序摧毀第 i 條**後**的數量）
   union(edges[del[i]].u, edges[del[i]].v);
6. 順序輸出 res[1..Q]。

關鍵代碼

#include 
#include 
const int MAX = 100005;
int fa[MAX], x[MAX], y[MAX], del[MAX], res[MAX];
bool isDel[MAX];

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void unite(int a, int b) {
    a = find(a); b = find(b);
    if (a != b) { fa[b] = a; ans--; }
}

int main() {
    int n, m;
    while (~scanf("%d%d", &n, &m)) {
        for (int i = 1; i <= m; ++i) scanf("%d%d", &x[i], &y[i]);
        int q; scanf("%d", &q);
        memset(isDel, 0, sizeof(isDel));
        for (int i = 1; i <= q; ++i) { scanf("%d", &del[i]); isDel[del[i]] = true; }
        for (int i = 1; i <= n; ++i) fa[i] = i;
        int ans = n;
        for (int i = 1; i <= m; ++i) if (!isDel[i]) unite(x[i], y[i]);
        for (int i = q; i >= 1; --i) {
            res[i] = ans;
            unite(x[del[i]], y[del[i]]);
        }
        for (int i = 1; i < q; ++i) printf("%d ", res[i]);
        printf("%d\n", res[q]);
    }
    return 0;
}

複雜度

• 時間：O((M+Q) α(N)) ≈ O(M+Q)。
• 空間：O(N+M)。

關鍵點

• **逆向加邊**將「刪除」轉化為「添加」，並查集完美支援添加邊合併。
• 結果數組 res[i] 存的是**加回第 i 條路前**的連通塊數，對應正序**摧毀第 i 條路後**的數量。
• 並查集路徑壓縮 + 按秩合併（或簡單啟發式）保證極快。

總結

CSUOJ 1601 是「離線動態連通性」的經典模板題：逆向思維 + 並查集。遇到「批量刪除邊/點後查詢連通性」類問題，首選逆向加邊離線並查集。