UVA 10765 Doves and bombs：雙連通分量與割點應用

問題描述

給定一個連通無向圖，刪除某個頂點後圖分裂成幾個連通塊。按連通塊數從多到少、頂點編號從大到小輸出前 m 個結果。

解題思路

利用 Tarjan 算法求雙連通分量（BCC）。割點屬於多個 BCC，刪除割點會使其所在的每個 BCC 分離成獨立連通塊。具體：

1. DFS 求 dfn, low，識別割點並用棧存儲邊，彈出形成 BCC。
2. 對每個 BCC，其中的割點刪除後連通塊數 +1。
3. 非割點刪除後連通塊數為 1（原圖連通）。
4. 統計每個頂點的連通塊數，按題目要求排序輸出。

代碼實現 (C++)

#include 
using namespace std;
const int MAXN = 10005;
struct Edge { int u, v; };
vector G[MAXN], bcc[MAXN];
stack stk;
int dfn[MAXN], low[MAXN], dfsTime, bccCnt;
bool isCut[MAXN];
int belong[MAXN]; // 點屬於哪些 BCC（多對多）

void tarjan(int u, int fa) {
    dfn[u] = low[u] = ++dfsTime;
    int child = 0;
    for (int v : G[u]) {
        if (!dfn[v]) {
            stk.push({u, v});
            ++child;
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u]) {
                isCut[u] = true;
                ++bccCnt;
                bcc[bccCnt].clear();
                while (true) {
                    Edge e = stk.top(); stk.pop();
                    if (belong[e.u] != bccCnt) { bcc[bccCnt].push_back(e.u); belong[e.u] = bccCnt; }
                    if (belong[e.v] != bccCnt) { bcc[bccCnt].push_back(e.v); belong[e.v] = bccCnt; }
                    if (e.u == u && e.v == v) break;
                }
            }
        } else if (v != fa && dfn[v] < dfn[u]) {
            stk.push({u, v});
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (fa == -1 && child == 1) isCut[u] = false; // 根特判
}

struct Node { int id, cnt; };
Node ans[MAXN];

int main() {
    int n, m;
    while (cin >> n >> m && (n || m)) {
        for (int i = 1; i <= n; ++i) {
            G[i].clear(); dfn[i] = low[i] = 0; isCut[i] = false; belong[i] = 0;
        }
        while (!stk.empty()) stk.pop();
        bccCnt = dfsTime = 0;
        for (int i = 0; i < m; ++i) {
            int u, v; cin >> u >> v;
            G[u].push_back(v); G[v].push_back(u);
        }
        tarjan(1, -1);
        for (int i = 1; i <= n; ++i) ans[i] = {i, 1}; // 非割點至少 1 塊
        for (int i = 1; i <= bccCnt; ++i) {
            for (int v : bcc[i]) {
                if (isCut[v]) ans[v].cnt++;
            }
        }
        sort(ans+1, ans+n+1, [](Node a, Node b){
            if (a.cnt != b.cnt) return a.cnt > b.cnt;
            return a.id > b.id;
        });
        for (int i = 1; i <= m; ++i) // 注意題目要求輸出前 m 個
            cout << ans[i].id << " " << ans[i].cnt << endl;
    }
    return 0;
}

複雜度分析

• 時間複雜度：O(n + m)。
• 空間複雜度：O(n + m)。

總結

本題將「刪除頂點後連通塊數」轉化為「頂點屬於多少個 BCC」，利用 Tarjan 求雙連通分量完美解決。注意根節點割點判定特例，以及非割點默認連通塊數為 1。