UVALive - 5135 Mining Your Own Business 双连通分量

时间:2021-11-28 04:28:34

题目链接:https://vjudge.net/problem/19845

题意:有N个矿井 ,由一些隧道连接起来,现在要修建尽量少的安全通道,使得无论哪里发生事故,所有人均

能逃出,求建的最少的安全通道数量和方案数

解法:

建安全通道的话,肯定不能建在割顶,因为割顶如果崩塌了,割顶所连接的双连通分量内的点就跑不掉了,还

得在双连通分量里面再建点(上述为双连通分量内部只有一个割顶的情况),这样不划算,还不如直接在里面建

点 。如果一个双连通分量的内部割顶有多个的话,那么在这个双连通分量里面就可以不用建安全通道了,因

为一个割顶崩塌了,还有其他点可以连向外面,所以,只考虑内部只有一个割顶的双连通分量要怎么建安全通

道。怎么建呢,排除掉割顶的所有的点都可以建。假设ans1代表所需要建立的安全通道的数量,ans2代表建

立的方案数,那么找到内部只有一个割顶的双连通分量时(双连通分量的内部结点有n个,排除掉割顶的话,还有

n-1种建立的方案) 那么ans1 = ans1 + 1; ans2 *= (n - 1)

如果给的图形成的是一个双连通分量(假设有n个点),只有一个,那么需要建立2个安全通道(一个倒塌了,

还有另一个),方案数为n * (n - 1) / 2

///UVALIVE 5135

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100100;
const int maxm = 1000010;
struct Edge{
int u, v;
Edge(int u=0, int v=0):u(u),v(v){}
}e[maxm];
int n,stamp,dfn[maxn],low[maxn],iscut[maxn],bccno[maxn];
int scnt,stk[maxm],bcc_cnt;
vector<int>vec[maxn],bcc[maxn];
void tarjan(int index, int fa){
int child=0,tmp;
dfn[index]=low[index]=++stamp;
for(int i=0; i<vec[index].size(); i++){
tmp=e[vec[index][i]].v;
if(!dfn[tmp]){
stk[++scnt]=vec[index][i], child++;
tarjan(tmp,index);
low[index]=min(low[index],low[tmp]);
if(low[tmp]>=dfn[index]){
iscut[index]=1;
bcc[++bcc_cnt].clear();
while(1){
int num=stk[scnt--];
if(bccno[e[num].u]!=bcc_cnt){
bcc[bcc_cnt].push_back(e[num].u);
bccno[e[num].u]=bcc_cnt;
}
if(bccno[e[num].v]!=bcc_cnt){
bcc[bcc_cnt].push_back(e[num].v);
bccno[e[num].v]=bcc_cnt;
}
if(e[num].u==index&&e[num].v==tmp)
break;
}
}
}
else if(dfn[tmp]<dfn[index]&&tmp!=fa){
stk[++scnt]=vec[index][i];
low[index]=min(low[index],dfn[tmp]);
}
}
if(fa<0&&child==1){
iscut[index]=0;
}
}

void find_bcc(){
memset(dfn, 0, sizeof(dfn));
memset(low, 0, sizeof(low));
memset(iscut, 0, sizeof(iscut));
memset(bccno, 0, sizeof(bccno));
memset(bcc, 0, sizeof(bcc));
stamp=scnt=bcc_cnt=0;
for(int i=1; i<=n; i++){
if(!dfn[i]){
tarjan(i,-1);
}
}
}


int main(){
int ks = 0;
while(scanf("%d", &n)!=EOF&&n){
for(int i=1; i<=maxn; i++) vec[i].clear();
int len = 0;
for(int i=1; i<=n; i++){
int u, v;
scanf("%d%d", &u,&v);
e[len] = Edge(u,v);
vec[u].push_back(len++);
e[len] = Edge(v,u);
vec[v].push_back(len++);
}
find_bcc();
long long ans1 = 0, ans2 = 1;
for(int i=1; i<=bcc_cnt; i++){
int cur_cnt=0;
for(int j = 0; j<bcc[i].size(); j++){
if(iscut[bcc[i][j]]) cur_cnt++;
}
if(cur_cnt==1){
ans1++;
ans2*=(long long)(bcc[i].size()-cur_cnt);
}
}
if(bcc_cnt==1){
ans1=2;
ans2=(long long)bcc[1].size()*(bcc[1].size()-1)/2;
}
printf("Case %d: %lld %lld\n", ++ks, ans1, ans2);
}
return 0;
}