题目地址：洛谷：【P3225】[HNOI2012]矿场搭建 – 洛谷、BZOJ：Problem 2730. — [HNOI2012]矿场搭建

题目描述

煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。
请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。

输入输出格式

输入格式：
输入文件有若干组数据，每组数据的第一行是一个正整数 N（N<=500），表示工地的隧道数，接下来的 N 行每行是用空格隔开的两个整数 S 和 T，表示挖 S 与挖煤点 T 由隧道直接连接。输入数据以 0 结尾。

输出格式：
输入文件中有多少组数据，输出文件 output.txt 中就有多少行。每行对应一组输入数据的 结果。其中第 i 行以 Case i: 开始（注意大小写，Case 与 i 之间有空格，i 与:之间无空格，: 之后有空格），其后是用空格隔开的两个正整数，第一个正整数表示对于第 i 组输入数据至少需 要设置几个救援出口，第二个正整数表示对于第 i 组输入数据不同最少救援出口的设置方案总 数。输入数据保证答案小于 2^64。输出格式参照以下输入输出样例。

输入输出样例

输入样例#1：

9
1 3
4 1
3 5
1 2
2 6
1 5
6 3
1 6
3 2
6
1 2
1 3
2 4
2 5
3 6
3 7
0

输出样例#1：

Case 1: 2 4
Case 2: 4 1

说明

Case 1 的四组解分别是(2,4),(3,4),(4,5),(4,6)；
Case 2 的一组解为(4,5,6,7)。

题解

我们考虑每个点双连通分量。一个点双中如果有不小于2个割点，就算一个割点坍塌，仍然可以通过另一个割点前往其他点双找救援出口；如果只有一个割点，那么割点坍塌了就不行了，需要找一个不是割点的点设置出口；如果没有割点，需要设置两个出口，因为万一一个塌了可以去另一个。
那么我们只需要处理一遍割点，然后DFS统计每个点双不包含割点在内的大小及割点数量，并统计出答案即可。

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>
#include <vector>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF 
        : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 10005;

int n, m;

std::vector<int> gra[MAXN];

int dfn[MAXN], low[MAXN], clk;
bool cut[MAXN];

inline void tarjan(int u, int fa) {
    int ch = 0;
    dfn[u] = low[u] = ++clk;
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        if(!dfn[v]) {
            ch++; tarjan(v, u);
            low[u] = std::min(low[u], low[v]);
            if(low[v] >= dfn[u]) cut[u] = true;
        } else if(dfn[v] < dfn[u] && v != fa) {
            low[u] = std::min(low[u], dfn[v]);
        }
    }
    if(ch == 1 && !fa) cut[u] = false;
}

int ccnt, siz, vis[MAXN], dclk;

inline void dfs(int u) {
    vis[u] = dclk; siz++;
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        if(vis[v] != dclk && cut[v]) {
            ccnt++; vis[v] = dclk;
        }
        if(!vis[v] && !cut[v]) dfs(v);
    }
}

int u, v;

int main() {
    for(int kase = 1;; kase++) {
        memset(dfn, 0, sizeof(dfn));
        memset(low, 0, sizeof(low));
        memset(cut, 0, sizeof(cut));
        memset(vis, 0, sizeof(vis));
        n = clk = dclk = 0;
        m = readint(); if(!m) break;
        for(int i = 1; i < MAXN; i++) gra[i].clear();
        for(int i = 1; i <= m; i++) {
            u = readint(); v = readint();
            gra[u].push_back(v);
            gra[v].push_back(u);
            n = std::max(n, std::max(u, v));
        }
        for(int i = 1; i <= n; i++) {
            if(!dfn[i]) tarjan(i, 0);
        }
        int ans1 = 0;
        LL ans2 = 1;
        for(int i = 1; i <= n; i++) {
            if(!vis[i] && !cut[i]) {
                dclk++; ccnt = siz = 0;
                dfs(i);
                if(!ccnt) {
                    ans1 += 2;
                    ans2 *= 1ll * siz * (siz - 1) / 2;
                } else if(ccnt == 1) {
                    ans1++;
                    ans2 *= siz;
                }
            }
        }
        printf("Case %d: %d %lld\n", kase, ans1, ans2);
    }
    return 0;
}