POJ 2793 Cactus：仙人掌生成子圖計數與高精度乘法

POJ 2793 Cactus：仙人掌生成子圖計數與高精度乘法

無向圖，求生成子圖（保留所有頂點，刪除部分邊）中為仙人掌的數量。仙人掌定義：連通且每條邊最多屬於一個簡單環。若原圖非仙人掌輸出 0。

關鍵觀察

• 生成子圖 = 刪除部分邊。要保持連通且為仙人掌，只能刪除環上的邊。
• 原圖為仙人掌 → 每條邊屬於至多一環。每個環可選：保留所有邊、或刪除恰好 1 條邊（打破環但保持連通）。
• 環長為 L 邊 → L+1 種選擇（刪 0 條或刪 1 條中的任一條）。
• 總方案數 = 所有環的 (長度+1) 乘積。

算法流程

1. Tarjan 求雙連通分量（邊雙連通/環）。
2. DFS 過程中用棧存邊，遇到割點/橋彈出構成一個塊。
3. 若塊邊數 > 1（即為環），方案數乘以 邊數+1。
4. 若某頂點屬於多個塊且非割點 → 非仙人掌，輸出 0。
5. 結果用 Java BigInteger 高精度存儲。

代碼邏輯

void tarjan(int u, int fa) {
    dfn[u] = low[u] = ++idx;
    for (i=head[u]; i!=-1; i=ed[i].next) {
        if (ed[i].flag) continue;
        ed[i].flag = ed[i^1].flag = true;
        st[++top] = i;
        v = ed[i].v;
        if (dfn[v]==-1) {
            tarjan(v, u); low[u]=min(low[u], low[v]);
            if (dfn[u] <= low[v]) { // 割點/橋，彈出一塊
                int num=0; do { j=st[top--]; num++; } while (i!=j);
                if (num>1) num++; res = res.multiply(BigInteger.valueOf(num));
            }
        } else low[u]=min(low[u], dfn[v]);
        if (low[v] < dfn[u]) f++; // 統計非樹邊
    }
    if (f > 1) res = BigInteger.ZERO; // 非仙人掌
}

複雜度

• Tarjan：O(V+E)。
• 高精度乘法：環數 ≤ V，乘積位數可大，BigInteger 處理。

本題將「仙人掌生成子圖計數」轉化為「環邊數+1 乘積」，Tarjan 邊雙連通分量分解是核心，Java 高精度省去手寫大數乘法麻煩。