煤矿工地可以看成是由隧道连接挖煤点组成的无向图。
为安全起见,希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。
于是矿主决定在某些挖煤点设立救援出口,使得无论哪一个挖煤点坍塌之后,其他挖煤点的工人都有一条道路通向救援出口。
请写一个程序,用来计算至少需要设置几个救援出口,以及不同最少救援出口的设置方案总数。
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int N=505,M=1005;
int n,m,dcc_cnt,root;
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],tim;
int stk[N],top;
bool cut[N];
vector<int> dcc[N];
void add(int a,int b){
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
void tarjan(int u){
dfn[u]=low[u]=++tim;
stk[++top]=u;
if(u==root&&h[u]==-1){
dcc_cnt++;
dcc[dcc_cnt].push_back(u);
return;
}
int cnt=0;
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(!dfn[j]){
tarjan(j);
low[u]=min(low[u],low[j]);
if(dfn[u]<=low[j]){
cnt++;
if(u!=root||cnt>1)
cut[u]=1;
++dcc_cnt;
int y;
do{
y=stk[top--];
dcc[dcc_cnt].push_back(y);
}while(y!=j);
dcc[dcc_cnt].push_back(u);
}
}
else
low[u]=min(low[u],dfn[j]);
}
}
int main(){
int T=1;
while(cin>>m,m){
for(int i=1;i<=dcc_cnt;i++)
dcc[i].clear();
memset(h,-1,sizeof(h));
memset(dfn,0,sizeof(dfn));
memset(cut,0,sizeof(cut));
idx=tim=n=dcc_cnt=top=0;
while(m--){
int a,b;
cin>>a>>b;
n=max(a,n);
n=max(n,b);
add(a,b);
add(b,a);
}
for(root=1;root<=n;root++)
if(!dfn[root])
tarjan(root);
int res=0;
ULL num=1;
for(int i=1;i<=dcc_cnt;i++){
int cnt=0;
for(int j=0;j<dcc[i].size();j++)
if(cut[dcc[i][j]])
cnt++;
if(cnt==0){
if(dcc[i].size()>1){
res+=2;
num*=dcc[i].size()*(dcc[i].size()-1)/2;
}
else
res++;
}
else if (cnt == 1) res ++, num *= dcc[i].size() - 1;
}
printf("Case %d: %d %llu\n", T ++, res, num);
}
return 0;
}
楼主你好,我想问一下这题为什么用不到bool in_stk[N] ?