题目描述
煤矿工地可以看成是由隧道连接挖煤点组成的无向图。
为安全起见,希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。
于是矿主决定在某些挖煤点设立救援出口,使得无论哪一个挖煤点坍塌之后,其他挖煤点的工人都有一条道路通向救援出口。
请写一个程序,用来计算至少需要设置几个救援出口,以及不同最少救援出口的设置方案总数。
输入格式
输入文件有若干组数据,每组数据的第一行是一个正整数 N,表示工地的隧道数。
接下来的 N 行每行是用空格隔开的两个整数 S 和 T,表示挖煤点 S 与挖煤点 T 由隧道直接连接。
输入数据以 0 结尾。
输出格式
每组数据输出结果占一行。
其中第 i 行以 Case i: 开始(注意大小写,Case 与 i 之间有空格,i 与:之间无空格,: 之后有空格)。
其后是用空格隔开的两个正整数,第一个正整数表示对于第 i 组输入数据至少需 要设置几个救援出口,第二个正整数表示对于第 i 组输入数据不同最少救援出口的设置方案总数。
输入数据保证答案小于 264,输出格式参照以下输入输出样例。
数据范围
1≤N≤500
样例
输入样例:
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
本题思路十分简单,用tarjan跑出所有的v_DCC和割点.
1.若此分量内有割点>1,则无论哪一个被堵,连通性依旧。贡献为0
2.若割点==1,则在割点及分量内任意一点各建一个,ans*=DCC.size()-1。贡献为1
3.若割点==0,则任建两个,ans=DCC.size()(DCC.size()-1)/2。贡献为2
奉上代码:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=5e4+10,MAXM=25e4+10;
struct edge{
int to,next;
}edges[MAXM<<1];
int head[MAXM],tot;
int n,m,ans1;
vector<int>v_DCC[MAXN];
bool cut_node[MAXN];
int cnt,num;ll ans2=1;
int dfn[MAXN],low[MAXN];
stack<int>s;
void add_edge(int u,int v)
{
edges[++tot].to=v;
edges[tot].next=head[u];
head[u]=tot;
}
void tarjan(int x)
{
dfn[x]=low[x]=++num;s.push(x);
int flag=0;
for(int i=head[x];i;i=edges[i].next)
{
int to=edges[i].to;
if(!dfn[to])
{
tarjan(to);
low[x]=min(low[x],low[to]);
if(low[to]>=dfn[x])
{
flag++;cnt++;int y=0;
if(x!=1||flag>1) cut_node[x]=true;
v_DCC[cnt].push_back(x);
do
{
y=s.top();s.pop();
v_DCC[cnt].push_back(y);
}
while(y!=to);
}
}
else low[x]=min(low[x],dfn[to]);
}
}
void Be_Clean()
{
memset(cut_node,0,sizeof(cut_node));
memset(edges,0,sizeof(edges));
memset(head,0,sizeof(head));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
while(s.size()) s.pop();
for(int i=1;i<=cnt;i++) v_DCC[i].clear();
ans1=num=cnt=tot=0;ans2=1;
}
int main()
{
for(int t=1;scanf("%d",&n)&&n;t++)
{
Be_Clean();
int ip1,ip2;int temp=n;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&ip1,&ip2);
add_edge(ip1,ip2);
add_edge(ip2,ip1);
temp=max(temp,max(ip1,ip2));
}
n=temp;
tarjan(1);//由于所有矿点联通,所以不用
/*
for(int i=1;i<=n;i++)
if(!dfn[i]) root=i,tarjan(i);
*/
for(int i=1;i<=cnt;i++)
{
int size=v_DCC[i].size(),sum=0;
for(int j=0;j<size;j++) sum+=cut_node[v_DCC[i][j]];
if(sum==1) ans1++,ans2*=size-1;
if(sum==0) ans1+=2,ans2*=size*(size-1)/2;
}
printf("Case %d: %d %lld\n",t,ans1,ans2);
}
}