Mining Your Own Business(点双联通)

题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=19845

大意：有一座地下矿， 有n条隧道相连， 任意两个连接点之间只有一条隧道相连接。 为了降低矿工的危险， 现在决定在连接点处建一些逃生装置， 使得不管哪个连接点倒塌， 不在此连接点的所有矿工都能逃生。 问安装最少的逃生装置， 及其安装的方案。

分析题可知， 这是求点双联通分量的， 我们只要把只有一个割点的点双联通分量安装一个逃生装置即可。 安装的方案数就是点双联通中节点的个数减去1； 而当只有一个点双联通分量时只需要安装两个逃生装置， 方案数就是v*(v-1)/2;

#include<stdio.h>
#include<string.h>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
const int maxn = 100000 + 10;
struct Edge
{
    int u, v;
    Edge(int i, int j) : u(i), v(j) {}
};
vector<int> G[maxn], bcc[maxn];
int low[maxn], dfn[maxn], bccno[maxn];
bool iscut[maxn];
int cur, cnt;
stack<Edge> S; //存边， 就不用处理割点可以同时存在不同的连通分量里了
void dfs(int u, int fa)
{
    dfn[u] = low[u] = ++cur;
    int child = 0;
    for(int i = 0; i < G[u].size(); i++)
    {
        int v = G[u][i];
        if(v == fa)
            continue;
        if(!dfn[v])
        {
            S.push(Edge(u, v));
            child++;
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if(dfn[u] <= low[v])  //u的子孙后代最早出现的时间不小于u出现的时间， u才能为割点
            {
                ++cnt;
                iscut[u] = true;
                bcc[cnt].clear();
                while(!S.empty())
                {
                    Edge x = S.top();
                    S.pop();
                    if(bccno[x.u] != cnt)
                    {
                        bcc[cnt].push_back(x.u);
                        bccno[x.u] = cnt;
                    }
                    if(bccno[x.v] != cnt)
                    {
                        bcc[cnt].push_back(x.v);
                        bccno[x.v] = cnt;
                    }
                    if(x.u==u && x.v==v)
                        break;
                }
            }
        }
        else if(dfn[v] < dfn[u])  //关于这个判断为什么不能用强联通和边双联通相同的 bccno[v]==0 判断， 请路过的大牛看到了给解释一下
        {
            S.push(Edge(u, v));
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(fa<0 && child==1)  //在起点只有子节点时，起点不是割点
        iscut[u] = false;
}
void find_bcc(int n)
{
    cur = cnt = 0;
    memset(dfn, 0, sizeof(dfn));
    memset(iscut, false, sizeof(iscut));
    memset(bccno, 0, sizeof(bccno));
    dfs(1, -1);
}
int main()
{
    int n, a, b, t = 0;
    int m = 0;
    while(scanf("%d", &n), n)
    {
        for(int i = 0; i <= m; i++)
            G[i].clear();
        for(int i = 0; i < n; i++)
        {
            scanf("%d%d", &a, &b);
            m = max(m, max(a, b));
            G[a].push_back(b);
            G[b].push_back(a);
        }
        find_bcc(n);
        long long ans1 = 0, ans2 = 1;
        for(int i = 1; i <= cnt; i++)
        {
            int cnt_cut = 0;
            for(int j = 0; j < bcc[i].size(); j++)
            {
                int k = bcc[i][j];
                if(iscut[k])
                    cnt_cut++;
            }
            if(cnt_cut == 1)
            {
                ans1++;
                ans2 *= (long long)(bcc[i].size()-cnt_cut);
            }
        }
        if(cnt == 1)
        {
            ans1 = 2;
            ans2 = bcc[cnt].size() * (bcc[cnt].size()-1) / 2;
        }
        printf("Case %d: %lld %lld\n", ++t, ans1, ans2);
    }
    return 0;
}