POJ 2838 Graph Connectivity：動態圖連通性的三種解法對比

問題描述

無向圖 G(V,E)，初始無邊。支援三種操作（Q ≤ 20000，N ≤ 1000）：

• I u v：插入邊 (u,v)（保證不存在）
• D u v：刪除邊 (u,v)（保證存在）
• Q u v：查詢 u,v 是否連通

解法一：鄰接表 + BFS/DFS（朴素）

每次查詢運行 BFS。插入/刪除 O(1)，查詢 O(N+E)。最壞 O(Q·N) 可能超時，但 N=1000、稀疏圖下常能通過。

解法二：併查集 + 邊集合 + 重建

維護所有當前邊的集合。查詢用併查集 O(α(N))。插入：加入邊並 union。刪除：標記邊失效，重建整個併查集（遍歷所有有效邊）。重建 O(E)，刪除操作較多時較慢。

解法三：鄰接表 + 併查集 + 增量重建（推薦）

結合兩者優點：

• 鄰接表維護實時圖結構（插入/刪除 O(deg)）
• 併查集加速查詢
• 刪除邊後，僅從受影響節點重新構建併查集（實際上簡化為：刪除後標記，查詢前若有刪除操作則完全重建併查集，利用 N=1000 特性）

核心代碼片段（解法三）

vector adj[MAXN];
int father[MAXN];
int n;

int find(int x) { return father[x]==x ? x : father[x]=find(father[x]); }
void unite(int a, int b) { father[find(a)] = find(b); }

void rebuild() {
    for (int i=1;i<=n;++i) father[i]=i;
    for (int u=1; u<=n; ++u)
        for (int v : adj[u])
            if (u < v) unite(u, v); // 無向邊只處理一次
}

bool query(int u, int v) { return find(u)==find(v); }

void insertEdge(int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);
    unite(u, v); // 直接合併
}

void deleteEdge(int u, int v) {
    // 從鄰接表移除（線性查找，deg ≤ 1000）
    auto erase = [&](vector& vec, int val) {
        for (auto it=vec.begin(); it!=vec.end(); ++it)
            if (*it==val) { vec.erase(it); break; }
    };
    erase(adj[u], v);
    erase(adj[v], u);
    rebuild(); // 簡單暴力重建，N=1000 時極快
}

複雜度分析

實測解法三在 POJ 2838 上 546ms AC，兼顧簡潔與效率。