题意：n条隧道由一些点连接而成，其中每条隧道链接两个连接点。任意两个连接点之间最多只有一条隧道。任务就是在这些连接点中，安装尽量少的太平井和逃生装置，使得不管哪个连接点倒塌，工人都能从其他太平井逃脱，求最少安装数量和方案。
分析：本题相当于在一张无向图上选择尽量少的点涂黑（对应太平井），使任意一个点被删除后，每个连通分量都至少还有一个黑点。不同的连通分量最多有一个公共点即割点，将割点涂上是不划算的，因为删除割点后，要保证每个连通分量还要有黑点，所以还要在其他的连通分量中涂黑点，如果不涂割点，还能省一个呢，在一个点连通分量中涂两个黑点也是不划算的， 所以只有当一个点连通分量中含有一个割点，那么就涂 除了 割点 其他的点，因为，如果删除这个割点后，你得保证剩下的有一个黑点。 对于一个连通分量中含有 >= 2个割点，就不用涂了，因为他有两个割点不会全部删除，可以通向其他的连通分量的 太平井，
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
typedef long long LL;
const int Max = ;
struct Edge
{
int u, v;
};
vector<int> G[Max], bcc[Max];
int pre[Max], bccno[Max], iscut[Max];
int dfs_clock, bcc_cnt;
stack<Edge> S;
int dfs(int u, int fa)
{
int lowu = pre[u] = ++dfs_clock;
int Size = G[u].size();
int child = ;
for (int i = ; i < Size; i++)
{
int v = G[u][i];
Edge e;
e.u = u;
e.v = v;
if (!pre[v])
{
S.push(e);
child++;
int lowv = dfs(v, u);
lowu = min(lowu, lowv);
if (lowv >= pre[u])
{
iscut[u] = true;
bcc_cnt++;
bcc[bcc_cnt].clear();
for (; ;)
{
Edge x = S.top();
S.pop();
if (bccno[x.u] != bcc_cnt)
{
bccno[x.u] = bcc_cnt;
bcc[bcc_cnt].push_back(x.u);
}
if (bccno[x.v] != bcc_cnt)
{
bccno[x.v] = bcc_cnt;
bcc[bcc_cnt].push_back(x.v);
}
if (x.u == u && x.v == v)
break;
}
}
}
else if (pre[v] < pre[u] && v != fa)
lowu = min(lowu, pre[v]);
}
if (child == && fa < )
iscut[u] = ;
return lowu;
}
void find_bcc(int n)
{
if (!S.empty())
S.pop();
memset(pre, , sizeof(pre));
memset(bccno, , sizeof(bccno));
memset(iscut, , sizeof(iscut));
dfs_clock = bcc_cnt = ;
for (int i = ; i <= n; i++)
{
if (!pre[i])
dfs(i, -);
}
}
int main()
{
int test = , n;
while (scanf("%d", &n) != EOF && n)
{
int u, v, temp = -;
for (int i = ; i < Max; i++)
G[i].clear(); //清空
for (int i = ; i <= n; i++)
{
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
temp = max(temp, max(u, v)); // 找到最大的点
}
find_bcc(temp); // 找连通分量
LL ans1 = , ans2 = ;
for (int i = ; i <= bcc_cnt; i++)
{
int cut_cnt = ;
int Size = bcc[i].size();
for (int j = ; j < Size; j++)
{
if (iscut[ bcc[i][j] ])
cut_cnt++;
}
if (cut_cnt == )
{
ans1++;
ans2 *= (LL)(Size - );
}
}
if (bcc_cnt == )
{
ans1 = ;
ans2 = (LL) bcc[].size() * (LL) (bcc[].size() - ) / ;
}
printf("Case %d: %lld %lld\n", ++test, ans1, ans2);
}
return ;
}