题意：n条隧道由一些点连接而成，其中每条隧道链接两个连接点。任意两个连接点之间最多只有一条隧道。任务就是在这些连接点中，安装尽量少的太平井和逃生装置，使得不管哪个连接点倒塌，工人都能从其他太平井逃脱，求最少安装数量和方案。
思路：其实本题就相当于在一张无向图中，涂尽量少的黑点，使得任意删除哪个点，每个连通分量至少有一个黑点。因为不同的连通分量最多只有一个公共点，那一定是割点。可以发现，涂黑割点是不划算的，而且在 一个点-双连通分量中涂黑两个黑点也是不划算的。所以只有当点-双连通分量只有一个割点时，才需要涂，而且是任选一个非割点涂黑。
2011年final题，想法不是很好明白，联系实际再YY一下就懂了
1 //struct ID 用来减小数字的，有点离散的作用。但是注释掉以后运行时间简短，AC 2 #include<cstdio> 3 #include<stack> 4 #include<vector> 5 #include<map> 6 #include<algorithm> 7 #include<cstring> 8 using namespace std; 9 typedef long long LL; 10 11 struct Edge { 12 int u, v; 13 }; 14 15 const int maxn = 100000 + 10; 16 int pre[maxn], iscut[maxn], bccno[maxn], dfs_clock, bcc_cnt; // 割顶的bccno无意义 17 vector<int> G[maxn], bcc[maxn]; 18 19 stack<Edge> S; 20 21 int dfs(int u, int fa) { 22 int lowu = pre[u] = ++dfs_clock; 23 int child = 0; 24 for(int i = 0; i < G[u].size(); i++) { 25 int v = G[u][i]; 26 Edge e = (Edge) { 27 u, v 28 }; 29 if(!pre[v]) { // 没有访问过v 30 S.push(e); 31 child++; 32 int lowv = dfs(v, u); 33 lowu = min(lowu, lowv); // 用后代的low函数更新自己 34 if(lowv >= pre[u]) { 35 iscut[u] = true; 36 bcc_cnt++; 37 bcc[bcc_cnt].clear(); 38 for(;;) { 39 Edge x = S.top(); 40 S.pop(); 41 if(bccno[x.u] != bcc_cnt) { 42 bcc[bcc_cnt].push_back(x.u); 43 bccno[x.u] = bcc_cnt; 44 } 45 if(bccno[x.v] != bcc_cnt) { 46 bcc[bcc_cnt].push_back(x.v); 47 bccno[x.v] = bcc_cnt; 48 } 49 if(x.u == u && x.v == v) break; 50 } 51 } 52 } else if(pre[v] < pre[u] && v != fa) { 53 S.push(e); 54 lowu = min(lowu, pre[v]); // 用反向边更新自己 55 } 56 } 57 if(fa < 0 && child == 1) iscut[u] = 0; 58 return lowu; 59 } 60 61 //struct ID { 62 // map<int, int> m; 63 // int cnt; 64 // ID():cnt(0) { } 65 // int get(int x) { 66 // if(!m.count(x)) m[x] = cnt++; 67 // return m[x]; 68 // } 69 //}; 70 71 int main() { 72 int kase = 0, n; 73 while(scanf("%d", &n) == 1 && n) { 74 memset(pre, 0, sizeof(pre)); 75 memset(iscut, 0, sizeof(iscut)); 76 memset(bccno, 0, sizeof(bccno)); 77 for(int i = 0; i < n*2; i++) G[i].clear(); 78 dfs_clock = bcc_cnt = 0; 79 80 // ID id; 81 for(int i = 0; i < n; i++) { 82 int u, v; 83 scanf("%d%d", &u, &v); 84 // u = id.get(u); 85 // v = id.get(v); 86 u--; 87 v--; 88 G[u].push_back(v); 89 G[v].push_back(u); 90 } 91 dfs(0, -1); // 调用结束后S保证为空，所以不用清空 92 93 LL ans1 = 0, ans2 = 1; 94 for(int i = 1; i <= bcc_cnt; i++) { 95 int cut_cnt = 0; 96 for(int j = 0; j < bcc[i].size(); j++) 97 if(iscut[bcc[i][j]]) cut_cnt++; 98 if(cut_cnt == 1) { 99 ans1++; 100 ans2 *= (LL)(bcc[i].size() - cut_cnt); 101 } 102 } 103 if(bcc_cnt == 1) { 104 ans1 = 2; 105 ans2 = bcc[1].size() * (bcc[1].size() - 1) / 2; 106 } 107 printf("Case %d: %lld %lld\n", ++kase, ans1, ans2); 108 } 109 return 0; 110 }