您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

BZOJ 3562 [SHOI2014] 神奇化合物：並查集縮點 + 刪除邊動態連通性 DFS 維護

編輯：C++ 入門

題目大意

n ≤ 5000 點，m ≤ 200,000 條初始邊，q ≤ 10,000 次操作。
操作：D a b 刪除邊，A a b 添加邊，Q 查詢當前連通塊數量。
邊刪除/添加僅針對初始邊集，無新增邊。

核心觀察：離線 + 縮點

標記所有**被刪除過**的邊（出現在 D 操作中）。
**從未被刪除**的邊，始終存在 → 可預先用**並查集**合併，縮點。
縮點後圖中點數 ≤ 2×(被刪除邊數) ≤ 20,000（每條邊貢獻兩端點）。
剩餘動態邊數 ≤ 20,000，操作數 10,000，可用**暴力 DFS** 維護連通性。

算法流程

讀入所有初始邊，存儲。
讀入所有操作，記錄 D 操作涉及的邊 → del[u][v] = true。
並查集合併所有 !del[u][v] 的初始邊 → 得到縮點映射 id[u]。
統計初始連通塊數 ans（並查集根數量）。
構建縮點圖：對每條初始邊，若 id[u] != id[v] 加入鄰接表（保留重邊計數 cnt[u][v]）。
處理操作序列：
- Q：輸出 ans。
- D a b：u=id[a], v=id[b]；cnt[u][v]--；若歸零且 !dfs(u,v) 則 ans++。
- A a b：u=id[a], v=id[b]；若 cnt[u][v]==0 && !dfs(u,v) 則 ans--；cnt[u][v]++。

DFS 連通性判斷

bool dfs(int u, int target) {
    if (u == target) return true;
    vis[u] = true;
    for (int v : adj[u]) {
        if (cnt[u][v] > 0 && !vis[v]) {
            if (dfs(v, target)) return true;
        }
    }
    return false;
}

由於縮點後圖較小，DFS 代價可接受（數據不強）。

完整代碼

#include 
using namespace std;

const int MAXN = 5005;
const int MAXM = 530005;

struct Edge { int to, next; } e[MAXM];
int head[MAXN], ecnt;
int dsu[MAXN];
bool del[MAXN][MAXN];
int cnt[MAXN][MAXN];
bool vis[MAXN];
int ans;

int find(int x) { return dsu[x]==x?x:dsu[x]=find(dsu[x]); }
void unite(int x, int y) { dsu[find(y)] = find(x); }

void addEdge(int u, int v) {
    e[ecnt] = {v, head[u]};
    head[u] = ecnt++;
}

bool dfs(int u, int t) {
    if (u == t) return true;
    vis[u] = true;
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to;
        if (cnt[u][v] > 0 && !vis[v]) {
            if (dfs(v, t)) return true;
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m; cin >> n >> m;
    vector> edges(m);
    for (auto &[u,v] : edges) cin >> u >> v;

    int q; cin >> q;
    struct Op { char type; int u, v; };
    vector ops(q);
    for (int i = 0; i < q; ++i) {
        cin >> ops[i].type;
        if (ops[i].type != 'Q') {
            cin >> ops[i].u >> ops[i].v;
            if (ops[i].type == 'D') del[ops[i].u][ops[i].v] = del[ops[i].v][ops[i].u] = true;
        }
    }

    // 1. 初始化 DSU
    iota(dsu+1, dsu+n+1, 1);
    memset(head, -1, sizeof(head));
    ecnt = 0;

    // 2. 合併永不刪除的邊
    for (auto [u,v] : edges) {
        if (!del[u][v]) unite(u, v);
    }

    // 3. 縮點映射
    for (int i = 1; i <= n; ++i) dsu[i] = find(i);

    // 4. 統計初始連通塊
    ans = 0;
    for (int i = 1; i <= n; ++i) if (dsu[i] == i) ++ans;

    // 5. 構建縮點圖（僅跨塊邊）
    for (auto [u,v] : edges) {
        int U = dsu[u], V = dsu[v];
        if (U != V) {
            cnt[U][V]++; cnt[V][U]++;
            if (cnt[U][V] == 1) { // 首條邊加入鄰接表
                addEdge(U, V);
                addEdge(V, U);
            }
        }
    }

    // 6. 處理操作
    for (auto &op : ops) {
        if (op.type == 'Q') {
            cout << ans << '\n';
        } else {
            int U = dsu[op.u], V = dsu[op.v];
            if (op.type == 'D') {
                if (--cnt[U][V] == 0) {
                    memset(vis, 0, sizeof(vis));
                    if (!dfs(U, V)) ++ans;
                }
            } else { // 'A'
                if (cnt[U][V] == 0) {
                    memset(vis, 0, sizeof(vis));
                    if (!dfs(U, V)) --ans;
                }
                ++cnt[U][V];
            }
        }
    }
    return 0;
}