题目链接：http://vjudge.net/contest/141787#problem/B
白书P318
题目大意：有N个矿井 ，由一些隧道连接起来，现在要修建尽量少的安全通道，使得无论哪里发生事故，所有人均能逃出，求建的最少的安全通道数量和方案数.
分情况讨论：
在一个无向图上选择尽量少的点涂黑，是的任意删除一个点后，每个连通分量都有一个黑点。
第一种情况：点-双连通里面没有割顶，那么至少要涂两个。
第二种情况：有一个割顶，那么割顶一定是不要涂黑的。涂黑了割顶，割顶删掉，那么在那个点-双连通里面还得加一个点涂黑。
第三种情况：有两个或两个以上的割顶，那么，一个点删掉以后，其他点都可以通过另外的割顶逃到相应的黑点上去。
求出点-双连通以后，查每个点-双连通分量的割顶数目就行了。
#include <bits/stdc++.h>
using namespace std; const int maxn = *; int n;
struct Edge
{
int u,v;
}; int pre[maxn], iscut[maxn], bccno[maxn], dfs_clock, bcc_cnt;
vector<int> G[maxn], bcc[maxn]; stack<Edge> S; int dfs(int u, int fa)
{
int lowu = pre[u] = ++dfs_clock;
int child = ;
for(int i = ; i < G[u].size(); i++)
{
int v = G[u][i];
Edge e = (Edge)
{
u, v
};
if(!pre[v]) // 没有访问过v
{
S.push(e);
child++;
int lowv = dfs(v, u);
lowu = min(lowu, lowv); // 用后代的low函数更新自己
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)
{
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(pre[v] < pre[u] && v != fa)
{
S.push(e);
lowu = min(lowu, pre[v]); // 用反向边更新自己
}
}
if(fa < && child == ) iscut[u] = ;
return lowu;
} void find_bcc(int n)
{ memset(pre,,sizeof(pre));
memset(iscut,,sizeof(iscut));
memset(bccno,,sizeof(bccno)); dfs_clock = bcc_cnt = ;
for(int i=; i<n; i++)
{
if(!pre[i])
dfs(i,-);
} } int main()
{
int kase = ;
while(scanf("%d",&n),n)
{
for(int i=; i<n*; i++)
{
G[i].clear();
} for(int i=; i<n; i++)
{ int u,v;
scanf("%d%d",&u,&v);
u--;
v--; G[u].push_back(v);
G[v].push_back(u); } //求点-双连通分量
find_bcc(n); long long ans1 = ,ans2 = ;
for(int i=; i<=bcc_cnt; i++)
{
int cut_cnt = ;
for(int j=; j<bcc[i].size(); j++)
{
if(iscut[bcc[i][j]])
cut_cnt ++;
}
if(cut_cnt==)
{
ans1 ++;
ans2 = ans2 * (bcc[i].size()-cut_cnt);
}
}
if(bcc_cnt==)
{
ans1 = ;
ans2 = bcc[].size() * (bcc[].size()-)/;
}
printf("Case %d: %lld %lld\n",kase++,ans1,ans2); } return ;
}