题意：n条隧道由一些点连接而成，其中每条隧道链接两个连接点。任意两个连接点之间最多只有一条隧道。任务就是在这些连接点中，安装尽量少的太平井和逃生装置，使得不管哪个连接点倒塌，工人都能从其他太平井逃脱，求最少安装数量和方案。
分析：本题相当于在一张无向图上选择尽量少的点涂黑（对应太平井），使任意一个点被删除后，每个连通分量都至少还有一个黑点。不同的连通分量最多有一个公共点即割点，将割点涂上是不划算的，因为删除割点后，要保证每个连通分量还要有黑点，所以还要在其他的连通分量中涂黑点，如果不涂割点，还能省一个呢，在一个点连通分量中涂两个黑点也是不划算的， 所以只有当一个点连通分量中含有一个割点，那么就涂 除了 割点 其他的点，因为，如果删除这个割点后，你得保证剩下的有一个黑点。 对于一个连通分量中含有 >= 2个割点，就不用涂了，因为他有两个割点不会全部删除，可以通向其他的连通分量的 太平井，
1 #include <iostream>View Code
2 #include <cstring>
3 #include <algorithm>
4 #include <cstdio>
5 #include <vector>
6 #include <stack>
7 using namespace std;
8 typedef long long LL;
9 const int Max = 50005;
10 struct Edge
11 {
12 int u, v;
13 };
14 vector<int> G[Max], bcc[Max];
15 int pre[Max], bccno[Max], iscut[Max];
16 int dfs_clock, bcc_cnt;
17 stack<Edge> S;
18 int dfs(int u, int fa)
19 {
20 int lowu = pre[u] = ++dfs_clock;
21 int Size = G[u].size();
22 int child = 0;
23 for (int i = 0; i < Size; i++)
24 {
25 int v = G[u][i];
26 Edge e;
27 e.u = u;
28 e.v = v;
29 if (!pre[v])
30 {
31 S.push(e);
32 child++;
33 int lowv = dfs(v, u);
34 lowu = min(lowu, lowv);
35 if (lowv >= pre[u])
36 {
37 iscut[u] = true;
38 bcc_cnt++;
39 bcc[bcc_cnt].clear();
40 for (; ;)
41 {
42 Edge x = S.top();
43 S.pop();
44 if (bccno[x.u] != bcc_cnt)
45 {
46 bccno[x.u] = bcc_cnt;
47 bcc[bcc_cnt].push_back(x.u);
48 }
49 if (bccno[x.v] != bcc_cnt)
50 {
51 bccno[x.v] = bcc_cnt;
52 bcc[bcc_cnt].push_back(x.v);
53 }
54 if (x.u == u && x.v == v)
55 break;
56 }
57 }
58 }
59 else if (pre[v] < pre[u] && v != fa)
60 lowu = min(lowu, pre[v]);
61 }
62 if (child == 1 && fa < 0)
63 iscut[u] = 0;
64 return lowu;
65 }
66 void find_bcc(int n)
67 {
68 if (!S.empty())
69 S.pop();
70 memset(pre, 0, sizeof(pre));
71 memset(bccno, 0, sizeof(bccno));
72 memset(iscut, 0, sizeof(iscut));
73 dfs_clock = bcc_cnt = 0;
74 for (int i = 1; i <= n; i++)
75 {
76 if (!pre[i])
77 dfs(i, -1);
78 }
79 }
80 int main()
81 {
82 int test = 0, n;
83 while (scanf("%d", &n) != EOF && n)
84 {
85 int u, v, temp = -1;
86 for (int i = 1; i < Max; i++)
87 G[i].clear(); //清空
88 for (int i = 1; i <= n; i++)
89 {
90 scanf("%d%d", &u, &v);
91 G[u].push_back(v);
92 G[v].push_back(u);
93 temp = max(temp, max(u, v)); // 找到最大的点
94 }
95 find_bcc(temp); // 找连通分量
96 LL ans1 = 0, ans2 = 1;
97 for (int i = 1; i <= bcc_cnt; i++)
98 {
99 int cut_cnt = 0;
100 int Size = bcc[i].size();
101 for (int j = 0; j < Size; j++)
102 {
103 if (iscut[ bcc[i][j] ])
104 cut_cnt++;
105 }
106 if (cut_cnt == 1)
107 {
108 ans1++;
109 ans2 *= (LL)(Size - 1);
110 }
111 }
112 if (bcc_cnt == 1)
113 {
114 ans1 = 2;
115 ans2 = (LL) bcc[1].size() * (LL) (bcc[1].size() - 1) / 2;
116 }
117 printf("Case %d: %lld %lld\n", ++test, ans1, ans2);
118 }
119 return 0;
120 }