hdu 3844 Mining Your Own Business

见刘汝佳训练指南P318  
#pragma comment(linker, "/STACK:1024000000,1024000000")  
#include <iostream>  
#include <stack>  
#include <queue>  
#include <cstdio>  
#include <cstdlib>  
#include <cmath>  
#include <set>  
#include <vector>  
#include <cstring>  
#include <algorithm>  
  
#define INF 0x3fffffff  
#define N 50010  
#define M 1000010  
#define LL long long  
#define mod 95041567  
  
using namespace std;  
  
struct Node{  
    int u, v;  
    Node(int x = 0, int y = 0){   
        u = x;  
        v = y;  
    }  
};  
  
Node G[N];  
int dfs_clock, bcc_cnt, G_len;  
int head[N], next[N * 2][2], pre[N], bccno[N];  
bool iscut[N];  
vector<int> bcc[N];  
  
void init(int n){  
    for(int i = 0; i <= n + 1; ++ i)   
        head[i] = -1, iscut[i] = 0, pre[i] = bccno[i] = 0;  
    dfs_clock = bcc_cnt = G_len = 0;  
}  
  
void add(int u, int v){  
    next[dfs_clock][1] = v;  
    next[dfs_clock][0] = head[u];  
    head[u] = dfs_clock ++;  
}  
  
int dfs(int u, int fa){  
    int child = 0;  
    pre[u] = ++ dfs_clock;  
    int lowu = pre[u];  
    for(int i = head[u]; i != -1; i = next[i][0]){  
        int v = next[i][1];  
        if(! pre[v]){  
            G[G_len ++] = Node(u, v);  
            ++ child;  
            int lowv = dfs(v, u);  
            lowu = min(lowu, lowv);  
            if(lowv >= pre[u]){  
                iscut[u] = true;  
                bcc[++ bcc_cnt].clear();  
                while(1){  
                    Node k = G[-- G_len];  
                    if(bccno[k.u] != bcc_cnt){  
                        bcc[bcc_cnt].push_back(k.u);  
                        bccno[k.u] = bcc_cnt;  
                    }  
                    if(bccno[k.v] != bcc_cnt){  
                        bcc[bcc_cnt].push_back(k.v);  
                        bccno[k.v] = bcc_cnt;  
                    }  
                    if(k.u == u && k.v == v) break;  
                }  
            }  
        }  
        else if(pre[u] > pre[v] && v != fa){  
            G[G_len ++] = Node(u, v);  
            lowu = min(lowu, pre[v]);  
        }  
    }  
    if(fa < 0 && child == 1) iscut[u] = 0;  
    return lowu;  
}  
  
int main()  
{  
  //  freopen("in.txt","r",stdin);  
    int n, t = 0;  
    while(scanf("%d", &n) != EOF){  
        if(! n) break;  
        init(n);  
        int u, v;  
        for(int i = 0; i < n; ++ i){  
            scanf("%d %d", &u, &v);  
            -- u, -- v;  
            add(u, v);  
            add(v, u);  
        }  
        dfs_clock = 0;  
        dfs(0, -1);  
        if(bcc_cnt == 1){  
            LL c = bcc[1].size();  
            printf("Case %d: 2 %I64d\n", ++t, c * (c - 1) / 2);  
            continue;  
        }  
        v = 0;  
        LL c = 1;  
        for(int i = 1; i <= bcc_cnt; ++ i){  
            int cnt = 0;  
            for(int j = bcc[i].size() - 1; j >= 0 && cnt < 2; -- j)  
                if(iscut[bcc[i][j]]) ++ cnt;  
            if(cnt == 1) ++ v, c *= (LL)(bcc[i].size() - 1);  
        }  
        printf("Case %d: %d %I64d\n", ++t, v, c);  
    }  
    return 0;  
}