例3

例3 矿场搭建

矿场搭建

煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。

请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。

倘若删掉的是割点，那么得到的每一个连通块都要保证至少一个出口，因此，我们找到图的所有割点。去掉割点后的连通块视为一个整体（点双连通分量）。如下图所示：

每个只和一个割点相连的连通块，必须设置一个出口，方案数量为该连通块的点的数量。
如果一个连通块和多个割点相连，那么该区域不需要设置出口，因为即使删掉一个割点，也能从其他路线出逃。

因此，删掉所有割点，统计所有只和一个割点相连的连通块的节点数量，需要设置的出口数量为这些连通块的数量，方案数为这些连通块的节点数量的乘积。

注意特殊情况，若整个图不存在割点，那么需要设置两个出口，这样才能保证如果删掉了一个设置出口的节点，可以从另一个出口逃出。方案数量为 $C_n^2$ 。

具体实现时，首先求出所有割点，接下来，从每个未曾访问过的非割点开始搜索，统计每个连通块的节点数量，以及和本连通块相连的割点数量，更新答案。

#include <bits/stdc++.h>
using namespace std;

const int N = 200 + 5, M = 500 + 10;
int head[N], ver[M << 1], nxt[M << 1], tot;
int m;
int dfn[N], low[N], tim;
bool cut[N];
int tot_cut;
int v[N];
int ans1;
long long ans2;

void add(int x, int y) {
    ver[++tot] = y, nxt[tot] = head[x], head[x] = tot;
}

void tarjan(int x) {
    dfn[x] = low[x] = ++tim;
    int flag = 0;
    for  (int i = head[x]; i; i = nxt[i]) {
        int y = ver[i];
        if (!dfn[y]) {
            tarjan(y);
            low[x] = min(low[x], low[y]);
            if (dfn[x] <= low[y]) {
                flag++;
                if (x  != 1 || flag > 1) tot_cut++, cut[x] = true;
            }
        } else low[x] = min(low[x], dfn[y]);
    }
}

void bfs(int t) {
    queue<int> q;
    q.push(t);
    v[t] = t;
    int sum = 1, connect_cut = 0;
    while (q.size()) {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = nxt[i]) {
            int y = ver[i];
            if (v[y] == t) continue;
            if (cut[y] && v[y] != t) { v[y] = t; connect_cut++; continue; }
            v[y] = t, sum++;
            q.push(y);
        }
    }
    if (connect_cut == 1) ans1++, ans2 *= sum;
}

int main() {
    int Case = 0;
    while (cin >> m && m) {
        tot = 1;
        memset(head, 0, sizeof head);
        memset(v, 0, sizeof v);
        memset(cut, 0, sizeof cut);
        memset(low, 0, sizeof low);
        memset(dfn, 0, sizeof dfn);
        
        tot_cut = 0;
        Case++;
        int n = 0;
        tot = 1;
        for (int i = 1; i <= m; i++) {
            int s, t; cin >> s >> t;
            add(s, t), add(t, s);
            n = max({n, s, t});
        }
        tarjan(1);
        ans1 = 0, ans2 = 1;
        if (tot_cut == 0) {
            ans1 = 2, ans2 = n * (n - 1) / 2;
        } else {
            for (int i = 1; i <= n; i++) {
                if (!v[i] && !cut[i]) {
                    bfs(i);
                }
            }
        }
        printf("Case %d: %d %lld\n", Case, ans1, ans2);
    }
}

例3 矿场搭建​

例3 矿场搭建