P3225 [HNOI2012]矿场搭建 tarjan

// 题意：在一幅无向图图上，删除一个点后，其他所有点上的人还能通过其他点出去，问最少设置几个出口，以及方案数
// 思路：无向图就联想到双联通分量，我们来分类讨论一下
//       1.假设图是一条链，那么我们要保证这个链上至少有两个出口，因为一旦这个链断开，人只能向两侧跑
//       2.假设图是一个双联通图，那么也至少要两个，因为要保证不是出口恰好被ban
//       
//       3.普通情况的话，我们可以想到将原图缩点后，整个图就形成了一棵树了，这个时候就不用考虑双联通分量内部了，那么这种情况下要满足要求，就只能是
//         任意一条树链两端都能到出口。 
//         有之前那道树链覆盖的题的经验，我们可以考虑极端之下，我们把树链尽量延长，那么树链的两头就变成了两个叶子节点
//         于是乎我们发现只要在两头的叶子节点设计出口即可。
//         设想我们如果不是在叶子节点设立，而是在叶子节点上一个节点设立，叶子结点就不满足可以两头跑的特性，我们就要多设立出口在叶子节点
//         所以我们的策略是最优解
//         
//         另外无向图中的叶子结点可以看做是只有一个割点的节点
//
#include<bits/stdc++.h>
using namespace std;
const int N = 1000 + 7;
int m, cnt, ct, ans1;
long long ans2;
vector<int> e[N];
int dfn[N], low[N], idx, cut[N], id;
stack<int> stk;
vector<int> mp[N];
void dfs(int u, int f) {
    dfn[u] = low[u] = ++idx;
    int ch = 0;
    stk.push(u);
    for (auto v : e[u]) {
        if (!dfn[v]) {
            dfs(v, u);
            ch++;
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u]) {
                id++;
                int temp = 0;
                while (1) {
                    temp = stk.top();
                    mp[id].push_back(temp);//因为一个割点可能属于多个双联通分量，所以我们每个都放这个割点，做完后再统计每个分量有多少个割点
                    if (temp == u) break;
                    stk.pop();
                }
                if (u != 1 || ch > 1) cut[u] = 1;
            }
        }
        else if (v != f) {
            low[u] = min(low[u], dfn[v]);
        }
    }
}
void init() {
    stk = stack<int>();
    cnt = 0;
    memset(cut, 0, sizeof(cut));
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    for (int i = 1; i <= id; i++) mp[i].clear();
    idx = id = 0;
    for (int i = 1; i <= N - 1; i++) e[i].clear();
    ans1 = 0, ans2 = 1;
}
int main() {
    while (cin >> m, ++ct) {
        if (m == 0) break;
        init();
        int a, b;
        for (int i = 1; i <= m; i++) {
            cin >> a >> b;
            e[a].push_back(b); e[b].push_back(a);
        }
        dfs(1, -1);//应该是连通图
        for (int i = 1; i <= id; i++) {
            int v1 = mp[i].size(), v2 = 0;
            for (auto x : mp[i]) if (cut[x]) v2++;
            if (v2 == 1) ans1++, ans2 *= v1 - 1;
            if (v2 == 0) ans1 += 2, ans2 *= v1 * (v1 - 1) / 2;
        }
        printf("Case %d: %d %lld\n", ct, ans1, ans2);
    }
    return 0;
}