POJ 1523 SPF：割點與點雙連通分量的 Tarjan 算法應用

問題描述

給定無向圖，移除某個頂點後，圖會分裂成多少個連通分量？對每個頂點輸出該數值。若無割點，輸出 "No SPF nodes"。

核心理論：割點與點雙連通分量

• 割點：移除後圖的連通分量數增加的頂點。
• 點雙連通分量 (BCC)：極大的無割點子圖。任意兩點之間至少有兩條不共頂點的路徑。
• 一個割點屬於多個 BCC，非割點屬於恰好一個 BCC。

Tarjan 算法求割點與 BCC

維護 dfn[u]（時間戳）、low[u]（能回溯到的最早祖先）。DFS 過程中：

• 若 u 是根且子樹數 > 1，則 u 是割點。
• 若 u 非根且存在子樹 v 滿足 low[v] >= dfn[u]，則 u 是割點，且 u 將該子樹對應的 BCC 分離。

計算移除頂點後的連通分量數

• 對非根割點 u：分量數 = cnt[u] + 1（cnt[u] 為 u 作為割點分離出的 BCC 數，+1 為包含父親的那塊）。
• 對根割點 u：分量數 = cnt[u]（根無父親，子樹數即分量數）。
• 非割點：分量數 = 1（移除後不增加分量）。

關鍵代碼結構

struct Edge { int u, v; };
vector G[MAXN];
stack S;
int dfn[MAXN], low[MAXN], dfs_clock;
int bcc_cnt, bccno[MAXN];
bool iscut[MAXN];
int cnt[MAXN]; // 割點分離的 BCC 數
bool is_root[MAXN];

void dfs(int u, int fa) {
    dfn[u] = low[u] = ++dfs_clock;
    int child = 0;
    for (int v : G[u]) {
        if (!dfn[v]) {
            S.push({u, v});
            child++;
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u]) {
                iscut[u] = true;
                cnt[u]++;
                // 彈出棧中邊形成一個 BCC
                bcc_cnt++;
                while (true) {
                    Edge e = S.top(); S.pop();
                    if (bccno[e.u] != bcc_cnt) { bcc[bcc_cnt].push_back(e.u); bccno[e.u] = bcc_cnt; }
                    if (bccno[e.v] != bcc_cnt) { bcc[bcc_cnt].push_back(e.v); bccno[e.v] = bcc_cnt; }
                    if (e.u == u && e.v == v) break;
                }
            }
        } else if (dfn[v] < dfn[u] && v != fa) {
            S.push({u, v});
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (fa == -1 && child == 1) iscut[u] = false; // 根只有一個子樹不是割點
    is_root[u] = (fa == -1);
}

輸出處理

for (int i = 0; i < n; ++i) {
    if (iscut[i]) {
        if (is_root[i]) ans.push_back({i+1, cnt[i]});
        else ans.push_back({i+1, cnt[i] + 1});
    }
}

複雜度與注意點

• 時間 O(V + E)，空間 O(V + E)。
• 並查集不可用（需動態連通性），必須用 Tarjan。
• 棧存儲邊而非點，方便 BCC 重建。
• 多測試用例需完整重置全局變量。

總結

POJ 1523 是點雙連通分量與割點應用的經典題。掌握「割點分離 BCC」的棧式 Tarjan 實現，並正確計算「移除頂點後的連通分量數 = 子 BCC 數 + (非根?1:0)」，是解決此類問題的關鍵。