HNOI 2012
煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。
请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。
输入文件有若干组数据，每组数据的第一行是一个正整数N，表示工地的隧道数，接下来的N行每行是用空格隔开的两个整数 S 和 T，表示挖煤点 S 与挖煤点 T 由隧道直接连接。输入数据以 0 结尾。
输入文件中有多少组数据，输出文件中就有多少行。每行对应一组输入数据的结果。
其中第 i 行以 Case i: 开始（注意大小写，Case 与 i 之间有空格，i 与 : 之间无空格，: 之后有空格），其后是用空格隔开的两个正整数，第一个正整数表示对于第 i 组输入数据至少需要设置几个救援出口，第二个正整数表示对于第 i 组输入数据不同最少救援出口的设置方案总数。
输出格式参照以下输入输出样例。
9
1 3
4 1
3 5
1 2
2 6
1 5
6 3
1 6
3 2
6
1 2
1 3
2 4
2 5
3 6
3 7
0
Case 1: 2 4
Case 2: 4 1
Case 1 的四组解分别是 (2,4),(2,5),(4,6)，(4,5)；
Case 2 的一组解为 (4,5,6,7)。
N<=500，输入数据保证答案小于2^64 。
____________________________________________________________
tarjan，求点双联通问题。
初步判断：
1、双联通里面只有有两个救援井就可以了，因为可以两两到达。即使是刚好哦一个救援井坏了也可以逃生。
2、如果矿井排成了一条线，要将救援井安排在两端，这样随便哪一个坏了可以从另一个逃生。中间不能安排救援井，如果它坏了，一端的矿井无法逃生。
所以，方法是：
把双联通分量缩点，图变成了一棵树，同时统计每个分量里面有几个割点。
如果有一个，他就是1中的端点，如果有两个或以上就是中间点。
有个特殊情况，整个图就是一个双联通图。
中间点不必管
单个点就看对应分量里面的点数，点数加2，方案数（n-1）。
双联通分量，n*(n-1)/2
注意：
1、点双联通分量标志点的判断。
2、这个题塌陷的是矿井，也就是点，靠点联通，所以是点双联通，开始没有想到！！！
____________________________________________________________
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=505; 4 int n,m; 5 struct edge 6 { 7 int u,v,nxt; 8 }e[maxn<<1]; 9 int head[maxn],js; 10 void addage(int u,int v) 11 { 12 e[++js].u=u;e[js].v=v; 13 e[js].nxt=head[u];head[u]=js; 14 } 15 int low[maxn],dfn[maxn],cnt,st[maxn],top,lts,ltn[maxn]; 16 bool cut[maxn]; 17 vector <int> lt[maxn]; 18 int du[maxn]; 19 void tarjan(int u,int rt) 20 { 21 low[u]=dfn[u]=++cnt; 22 st[++top]=u; 23 int ct=0; 24 for(int i=head[u];i;i=e[i].nxt) 25 { 26 int v=e[i].v; 27 if(!dfn[v]) 28 { 29 ct++; 30 tarjan(v,u); 31 low[u]=min(low[u],low[v]); 32 if((u==rt && ct>1) || (u!=rt && low[v]>=dfn[u]))cut[u]=1; 33 if(low[v]>=dfn[u]) 34 { 35 ++lts; 36 while(st[top]!=u)lt[lts].push_back(st[top--]); 37 lt[lts].push_back(u); 38 } 39 } 40 else low[u]=min(low[u],dfn[v]); 41 } 42 } 43 void init() 44 { 45 memset(head,0,sizeof head); 46 n=0; 47 js=0; 48 memset(cut,0,sizeof cut); 49 memset(low,0,sizeof low); 50 memset(dfn,0,sizeof dfn); 51 cnt=0; 52 top=0; 53 memset(ltn,0,sizeof ltn); 54 lts=0; 55 memset(du,0,sizeof du); 56 } 57 int cas=0; 58 int main() 59 { 60 while(scanf("%d",&m),m) 61 { 62 cas++; 63 init(); 64 for(int u,v,i=1;i<=m;++i) 65 { 66 scanf("%d%d",&u,&v); 67 addage(u,v);addage(v,u); 68 n=max(n,u);n=max(n,v); 69 } 70 for(int i=1;i<=n;++i)lt[i].clear(); 71 for(int i=1;i<=n;++i) 72 if(!dfn[i])tarjan(i,i); 73 long long jyk=0,fas=1; 74 for(int i=1;i<=lts;++i) 75 { 76 int tp=0,ln=lt[i].size(); 77 for(int j=0;j<ln;++j) 78 if(cut[lt[i][j]])++tp; 79 if(tp==0)jyk+=2,fas=fas*ln*(ln-1)/2; 80 else if(tp==1) jyk++,fas=fas*(ln-1); 81 } 82 cout<<"Case "<<cas<<": "<<jyk<<" "<<fas<<‘\n‘; 83 } 84 return 0; 85 }
原文：https://www.cnblogs.com/gryzy/p/10996692.html
