UVALive 5135 Mining Your Own Business（点双连通分量）

Problem:
有一个矿井（图），为了矿工的安全，无论哪一个点出现事故，所有地方的矿工都能安全逃出，问最少建多少个安全通道，有多少种方案？
Solution:
求出点双连通分量，每一个分量中任意一个除了割点的点都可以任选一个作为安全通道。
note:
当只有一个连通分量的时候，需要有两个安全通道。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#define eps 1e-6
#define LL long long
using namespace std;
const int maxn = 100100;

struct Edge {
int u, v;
    Edge(int u, int v) : u(u), v(v) {}
};
bool cut[maxn];
int low[maxn], dfn[maxn], bccno[maxn], clocks, bcc_cnt;
vector<int> G[maxn], bcc[maxn];
stack<Edge> S;
void tarjan(int u, int fa){
    low[u] = dfn[u] = ++clocks;
int child = 0;
for(int i = 0; i < G[u].size(); ++i){
int v = G[u][i];
        Edge e = Edge(u, v);
if(!dfn[v]){
            S.push(e);
            child++;
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
if(low[v] >= dfn[u]) {
                cut[u] = true;
                bcc_cnt++;  bcc[bcc_cnt].clear();//bcc >= 1;
while(1){
                    Edge t = S.top();  S.pop();
if(bccno[t.u] != bcc_cnt){
                        bcc[bcc_cnt].push_back(t.u);
                        bccno[t.u] = bcc_cnt;
                    }
if(bccno[t.v] != bcc_cnt){
                        bcc[bcc_cnt].push_back(t.v);
                        bccno[t.v] = bcc_cnt;
                    }
if(t.u==u && t.v==v)  break;
                }
            }
        }
else if(fa!=v && low[u]>dfn[v]) {
            S.push(e);
            low[u] = dfn[v];
        }
    }
if(fa==-1)
        cut[u] = (child>=2) ? true : false;
}

int m, n, kase;
void find_bcc(int n) {
memset(dfn, 0, sizeof(dfn));
memset(cut, 0, sizeof(cut));
memset(bccno, 0, sizeof(bccno));
    clocks = bcc_cnt = 0;
for(int i = 1; i < n; i++) {
if(!dfn[i])
            tarjan(i, -1);
    }
}

void init() {
int u, v;
for(int i = 0; i < maxn; i++)
        G[i].clear();
for(int i = 0; i < m; i++) {
scanf("%d%d", &u, &v);
        n = max(n, max(u, v));
        u--; v--;
        G[u].push_back(v);
        G[v].push_back(u);
    }
}

void solve() {
    find_bcc(n);
int tunnel = 0;
    LL tun_cnt = 1;
for(int i = 1; i <= bcc_cnt; i++) {
int cut_cnt = 0;
for(int j = 0; j < bcc[i].size(); j++) {
if(cut[bcc[i][j]]) cut_cnt++;
        }
if(cut_cnt == 1) {
            tun_cnt *= (LL)(bcc[i].size()-cut_cnt);
            tunnel++;
        }
else if(cut_cnt == 0) {
            tun_cnt *= (LL)(bcc[i].size())*(LL)(bcc[i].size()-1)/2;
            tunnel += 2;
        }
    }
printf("Case %d: %d %lld\n", ++kase, tunnel, tun_cnt);
}

int main() {
//freopen("input.txt", "r", stdin);
while(cin >> m && m) {
        init();
        solve();
    }
return 0;
}