【HNOI2012】bzoj2730 矿场搭建【解法一】

本文主要是介绍【HNOI2012】bzoj2730 矿场搭建【解法一】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description
煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。
Input

输入文件有若干组数据，每组数据的第一行是一个正整数 N（N≤500），表示工地的隧道数，接下来的 N 行每行是用空格隔开的两个整数 S 和
T，表示挖 S 与挖煤点 T 由隧道直接连接。输入数据以 0 结尾。 Output

输入文件中有多少组数据，输出文件 output.txt 中就有多少行。每行对应一组输入数据的结果。其中第 i 行以 Case i:
开始（注意大小写，Case 与 i 之间有空格，i 与:之间无空格，: 之后有空格），其后是用空格隔开的两个正整数，第一个正整数表示对于第
i 组输入数据至少需要设置几个救援出口，第二个正整数表示对于第 i 组输入数据不同最少救援出口的设置方案总数。输入数据保证答案小于
2^64。输出格式参照以下输入输出样例。

解法二见【这里】。
很明显跟bcc有关。那么先用tarjan求出bcc。
经过分析可以发现，当且仅当一个bcc只含有一个割点时，在它内部需要有一个出口。出口的选择方案是非割点的任何一个点。
但是注意一种特殊情况，即整张图就是自己的bcc，那么需要两个出口，方案数为n(n-1)/2。

#include<cstdio>
#include<cstring>
#include<vector>
#include<stack>
#include<iostream>
using namespace std;
#define M(a) memset(a,0,sizeof(a))
struct edge
{int f,t;
}e1,e2;
stack<edge> sta;
vector<edge> vec[1010];
vector<int> bcc[1010];
int m,n,clo,tot,dfn[1010],low[1010],bel[1010];
bool is[1010];
void in()
{int i,j,k,x,y,z;while (!sta.empty()) sta.pop();for (i=1;i<=1005;i++)vec[i].clear(),bcc[i].clear();tot=clo=n=0;M(dfn);M(low);M(is);M(bel);for (i=1;i<=m;i++){scanf("%d%d",&x,&y);vec[x].push_back((edge){x,y});vec[y].push_back((edge){y,x});n=max(n,x);n=max(n,y);}
}
void dfs(int x,int fa)
{int i,j,k,p,q,u,v,cnt=0;dfn[x]=low[x]=++clo;for (i=0;i<vec[x].size();i++)if (vec[x][i].t!=fa){u=vec[x][i].t;if (!dfn[u]){sta.push(vec[x][i]);dfs(u,x);cnt++;low[x]=min(low[x],low[u]);if (low[u]>=dfn[x]){is[x]=1;tot++;while (1){e1=sta.top();sta.pop();if (bel[e1.f]!=tot){bel[e1.f]=tot;bcc[tot].push_back(e1.f);}if (bel[e1.t]!=tot){bel[e1.t]=tot;bcc[tot].push_back(e1.t);}if (e1.f==x&&e1.t==u) break;}}}else{if (dfn[u]<dfn[x]) sta.push(vec[x][i]);low[x]=min(low[x],dfn[u]);}}if (fa==-1&&cnt==1) is[x]=0;
}
void find()
{for (int i=1;i<=n;i++)if (!dfn[i])dfs(i,-1);
}
void out()
{int i,j,k,cnt;long long ans1=0,ans2=1;if (tot==1){printf("2 %lld\n",(long long)n*(n-1)/2);return;}for (i=1;i<=tot;i++){cnt=0;for (j=0;j<bcc[i].size();j++)if (is[bcc[i][j]]) cnt++;if (cnt==1){ans1++;ans2*=(bcc[i].size()-1);}}printf("%lld %lld\n",ans1,ans2);
}
int main()
{int K=0;while (scanf("%d",&m)&&m){printf("Case %d: ",++K);in();find();out();}
}