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

题目链接：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;
}