UVA 1108 Mining Your Own Business：雙連通分量求最小安全點集

問題建模

連通無向圖，選最少「安全點」，使得任意非安全點塌方後，其餘點仍能到達某安全點。
等價於：找最小點集，使其與所有割點相鄰，且每個塊（Biconnected Component）至少有一個安全點或與安全點相連。

核心結論

• 若圖本身就是雙連通（無割點，bcc_cnt=1）：需 2 個安全點，方案數 = C(n,2)
• 否則：每個只含 1 個割點的 BCC（葉塊）必須放 1 個安全點（非割點處）
  方案數 = 所有葉塊的 (塊大小 - 1) 乘積

Tarjan 求 BCC（邊雙連通分量）

struct Edge { int u, v; };
vector g[N], bcc[N];
stack S;
int dfn[N], low[N], dfs_clock, bcc_cnt;
bool iscut[N];
int bccno[N];

void dfs_bcc(int u, int fa) {
    low[u] = dfn[u] = ++dfs_clock;
    int child = 0;
    for (int v : g[u]) {
        Edge e = {u, v};
        if (!dfn[v]) {
            S.push(e); child++;
            dfs_bcc(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u]) {
                iscut[u] = true;
                bcc_cnt++; bcc[bcc_cnt].clear();
                while (true) {
                    Edge x = S.top(); S.pop();
                    if (bccno[x.u] != bcc_cnt) { bcc[bcc_cnt].push_back(x.u); bccno[x.u] = bcc_cnt; }
                    if (bccno[x.v] != bcc_cnt) { bcc[bcc_cnt].push_back(x.v); bccno[x.v] = bcc_cnt; }
                    if (x.u == u && x.v == v) break;
                }
            }
        } else if (dfn[v] < dfn[u] && v != fa) {
            S.push(e);
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (fa < 0 && child == 1) iscut[u] = false; // 根節點特判
}

統計答案

void solve() {
    long long ans1 = 0, ans2 = 1;
    for (int i = 1; i <= bcc_cnt; i++) {
        int cut_cnt = 0;
        for (int v : bcc[i]) if (iscut[v]) cut_cnt++;
        if (cut_cnt == 1) { // 葉塊
            ans1++;
            ans2 *= (bcc[i].size() - cut_cnt); // 非割點數
        }
    }
    if (bcc_cnt == 1) { // 整圖雙連通
        ans1 = 2;
        ans2 = 1LL * bcc[1].size() * (bcc[1].size() - 1) / 2;
    }
    printf("%lld %lld\n", ans1, ans2);
}

關鍵點

• 邊雙連通分量：割邊分隔，而非割點。但本題用點雙連通（BCC）分析
• 葉塊：只含 1 個割點的 BCC，必須在其內部（非割點）放安全點
• 根節點特判：DFS 根若只有 1 個孩子，不是割點
• long long：方案數可能很大

經典雙連通分量應用，BCC 樹中葉塊對應必須放置安全點的區域。