HDU 4587 TWO NODES：雙連通分量與割點應用求最大連通塊數

題目大意

無向圖 N 點 M 邊。刪除 2 個點後，求剩餘圖中最大連通分量的點數最大值。輸出該最大值。

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

• 割點：刪除後連通分量數增加的點
• 雙連通分量 (BCC)：無割點的極大子圖
• 割點屬於多個 BCC，非割點屬於 1 個 BCC
• 刪除割點 u，其所在 BCC 會分裂，產生新連通分量

算法策略：兩次 Tarjan

1. 第一次 Tarjan：找出所有割點，並計算刪除每個割點後產生的連通分量數 (記為 cut[u])
2. 第二次枚舉：對每個割點 u，考慮再刪除一個點 v，計算最大連通分量

關鍵代碼片段

// 第一次 Tarjan：求割點及 cut[u]
int dfs(int u, int fa) {
    int lowu = dfn[u] = ++dfs_clock;
    int child = 0;
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to;
        if (v == del) continue;  // 第二次用：忽略已刪除點
        if (!dfn[v]) {
            child++;
            int lowv = dfs(v, u);
            lowu = min(lowu, lowv);
            if (lowv >= dfn[u]) cut[u]++;  // u 是割點，這條邊對應一個新分量
        } else if (dfn[v] < dfn[u]) {
            lowu = min(lowu, dfn[v]);
        }
    }
    if (fa == -1 && child == 1) cut[u] = 0;  // 根特判
    return lowu;
}

// 第二次：枚舉第一個刪除點 u (必須是割點)
for (int u = 1; u <= n; u++) if (cut[u] > 0) {
    del = u;
    memset(dfn, 0, sizeof(dfn));
    dfs_clock = 0;
    // 再次 Tarjan，但忽略 u，求在 u 被刪除後，再刪一個點的最大效果
    // 結合 cut[u] 和第二次結果計算答案
}

優化觀察

實際上，刪除兩點後的最大連通分量 = max(

• 原圖連通分量數 (無割點情況)
• 某割點 u 的 cut[u] + 1 (刪除 u 後的分量數)
• 兩個割點組合效果 (需枚舉)

但 n≤5000，可 O(n·(n+m)) 暴力枚舉第一點 + Tarjan 第二點，約 5000×10000 = 5e7，邊界可行。

完整代碼框架

#include 
using namespace std;
const int MAXN = 5005;
struct Edge { int to, next; } e[MAXN*4];
int head[MAXN], ecnt;
int dfn[MAXN], low[MAXN], dfs_clock;
int cut[MAXN];  // 割點產生的分量數
int del;        // 當前忽略的點

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

int dfs(int u, int fa) {
    int lowu = dfn[u] = ++dfs_clock;
    int child = 0;
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to;
        if (v == del) continue;
        if (!dfn[v]) {
            child++;
            int lowv = dfs(v, u);
            lowu = min(lowu, lowv);
            if (lowv >= dfn[u]) cut[u]++;
        } else if (dfn[v] < dfn[u]) {
            lowu = min(lowu, dfn[v]);
        }
    }
    if (fa == -1 && child == 1) cut[u] = 0;
    return lowu;
}

int main() {
    int n, m;
    while (~scanf("%d%d", &n, &m)) {
        // 讀圖、初始化
        // 第一次 Tarjan (del=-1) 求 cut[]
        // 枚舉 u=1..n, del=u, 第二次 Tarjan 更新答案
        // 輸出最大值
    }
    return 0;
}

複雜度分析

關鍵細節

1. 根節點特判：DFS 樹根是割點當且僅當有 ≥2 個子樹
2. 割點分量計數：cut[u] 初始為 0，每滿足 low[v] >= dfn[u] 遞增 1
3. 忽略點機制：全局 del 變量，DFS 時跳過
4. 邊雙連通 vs 點雙連通：本題涉及點雙連通 (割點)，邊雙連通對應橋

總結

HDU 4587 考察割點 Tarjan 算法的深度應用：割點分量計數 + 枚舉刪除點重跑 Tarjan。核心難點在於正確計算割點刪除後的連通分量數，並處理根節點特判。此類「刪除 k 個點最大化連通分量」問題，k=1 時單次 Tarjan，k=2 時枚舉+Tarjan，k≥3 通常需更高級結構 (如樹分解)。