题意
有一座地下稀有金属矿由n条隧道和一些连接点组成，其中每条隧道连接两个连接点。任意两个连接点之间最多只有一条隧道。为了降低矿工的危险，你的任务是在一些连接点处安装太平井和相应的逃生装置，使得不管哪个连接点倒塌，不在此连接点的多有矿工都能到达太平井逃生。为节约成本，你应当在尽量少的连接点安装太平井。还需要计算出当太平井的数目最小时的安装方案总数。
分析
1对于一个双连通分量，如果它有两个以上的割顶，则不需要建太平井。如果只有一个割顶，则任选一个非割顶的点建太平井。
2若整个图无割顶，则任涂两个点，方案数为n*（n-1）/2
3对于不属于双连通分量的点，只能在他们每个点都建一个太平井
1 #include <cstdio>
2 #include <cstring>
3 #include <iostream>
4 #include <algorithm>
5 #include <stack>
6 #include <vector>
7
8 using namespace std;
9 const int maxn=100000+100;
10 int n,sz,N;
11 int head[maxn],Next[maxn],to[maxn];
12 struct Edge{
13 int u,v;
14 };
15 void add_edge(int a,int b){
16 ++sz;
17 to[sz]=b;Next[sz]=head[a];head[a]=sz;
18 }
19 int ansn;
20 long long anss;
21 int pre[maxn],iscut[maxn],bccno[maxn],dfs_clock,bcc_cnt;
22 vector<int>bcc[maxn];
23 stack<Edge>S;
24 int dfs(int u,int fa){
25 int lowu=pre[u]=++dfs_clock;
26 int child=0;
27 for(int i=head[u];i!=-1;i=Next[i]){
28 int v=to[i];
29 Edge e=(Edge){u,v};
30 if(!pre[v]){
31 S.push(e);
32 child++;
33 int lowv=dfs(v,u);
34 lowu=min(lowu,lowv);
35 if(lowv>=pre[u]){
36 iscut[u]=1;
37 bcc_cnt++;bcc[bcc_cnt].clear();
38 for(;;){
39 Edge x=S.top();S.pop();
40 if(bccno[x.u]!=bcc_cnt){
41 bcc[bcc_cnt].push_back(x.u);
42 bccno[x.u]=bcc_cnt;
43 }
44 if(bccno[x.v]!=bcc_cnt){
45 bcc[bcc_cnt].push_back(x.v);
46 bccno[x.v]=bcc_cnt;
47 }
48 if(x.u==u&&x.v==v)break;
49 }
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 void find_bcc(int n){
61 memset(pre,0,sizeof(pre));
62 memset(iscut,0,sizeof(iscut));
63 memset(bccno,0,sizeof(bccno));
64 dfs_clock=bcc_cnt=0;
65 for(int i=1;i<=n;i++)
66 if(!pre[i])dfs(i,-1);
67 }
68 int kase;
69 int main(){
70 kase=0;
71 while(scanf("%d",&n)!=EOF&&n){
72 int a,b;
73 sz=0;
74 memset(head,-1,sizeof(head));
75 N=0;
76 ansn=0;
77 anss=1;
78 for(int i=1;i<=n;i++){
79 scanf("%d%d",&a,&b);
80 N=max(N,a);
81 N=max(N,b);
82 add_edge(a,b);
83 add_edge(b,a);
84 }
85 find_bcc(N);
86 for(int i=1;i<=bcc_cnt;i++){
87 int num=0;
88 for(int j=0;j<bcc[i].size();j++){
89 if(iscut[bcc[i][j]])
90 num++;
91 }
92 if(num==1){
93 ansn++;
94 anss*=(long long)(bcc[i].size()-1);
95 }
96 if(num==0){
97 ansn+=2;
98 anss*=(long long)bcc[i].size()*(long long)(bcc[i].size()-1)/2;
99 }
100 }
101 for(int i=1;i<=N;i++){
102 if(!bccno[i])
103 ansn++;
104 }
105 ++kase;
106 printf("Case %d: ",kase);
107 printf("%d %lld\n",ansn,anss);
108 }
109 return 0;
110 }
