[HNOI2012]矿场搭建

题意：
给出n条边，求该图至少需要设置多少个逃生点才能使无论哪一个点失去，其余点都能至少到达一个逃生点，并求出方案数。

思路：
考虑点双连通分量：
如果该点双连通分量只有一个割点，则需要设一个逃生点，且该点不能是割点（防止唯一的割点失去时其余点无法到达逃生点）。
如果该点双连通分量有大于一个割点，则无需设置逃生点，因为你至少可以通过一个割点到达另一个点双连通分量。
如果该点双连通分量没有割点，则需要设二个逃生点（防止设为逃生点的点失去时其余点无法到达逃生点）

代码：

#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

typedef long long ll;
const ll inf=1e9+7;

int n, vis[1005], dfn[1005], low[1005], cut[1005], ji;

ll ans1=0, ans2=1;

vector<int> g[1005];

void dfs(int v,int f)
{
    int child=0;
    dfn[v]=low[v]=ji++;
    for(int i=0; i<g[v].size(); i++)
    {
        int u=g[v][i];
        if(f!=u)
        {
            if(!dfn[u])
            {
                dfs(u,v);
                child++;
                low[v]=min(low[v],low[u]);
                if(low[u]>=dfn[v]&&f!=-1)
                {
                    //printf("asd %d\n",v);
                    cut[v]=1;
                }
            }
            else
            {
                low[v]=min(low[v],dfn[u]);
            }
        }
    }
    if(f==-1&&child>=2)
    {
        cut[v]=1;
    }
}

stack<int> st;

void solve(int v,int f)
{
    st.push(v);
    dfn[v]=low[v]=ji++;
    for(int i=0; i<g[v].size(); i++)
    {
        int u=g[v][i];
        if(f!=u)
        {
            if(!dfn[u])
            {
                solve(u,v);
                low[v]=min(low[v],low[u]);
                if(low[u]>=dfn[v])
                {
                    if(cut[v])
                    {
                        int di=1, p;
                        ll shu=1;
                        do
                        {
                            p=st.top();
                            st.pop();
                            shu++;
                            if(cut[p]==1)
                            {
                                di++;
                            }
                        }while(p!=u);
                        if(di==1)
                        {
                            ans1++;
                            ans2=ans2*(shu-1);
                        }
                    }
                }
            }
            else
            {
                low[v]=min(low[v],dfn[u]);
            }
        }
    }
}

int main()
{
    int ti=1;
    while(~scanf("%d",&n))
    {
        if(n==0)
        {
            break;
        }
        ji=1;
        ans1=0;
        ans2=1;
        for(int i=0; i<n; i++)
        {
            int u, v;
            scanf("%d%d",&u,&v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        printf("Case %d: ",ti++);
        memset(cut,0,sizeof(int)*(n+5));
        memset(dfn,0,sizeof(int)*(n+5));
        memset(low,0,sizeof(int)*(n+5));
        dfs(1,-1);
        memset(dfn,0,sizeof(int)*(n+5));
        memset(vis,0,sizeof(int)*(n+5));
        memset(low,0,sizeof(int)*(n+5));
        solve(1,-1);
        int p, di=0;
        ll shu=0;
        do
        {
            p=st.top();
            shu++;
            st.pop();
            if(cut[p])
            {
                di++;
            }

        }
        while(!st.empty());
        if(shu>1)
        {
            if(di==1&&shu>1)
            {
                ans1++;
                ans2=ans2*(shu-1);
            }
            else if(di==0)
            {
                ans1=2;
                ans2=shu*(shu-1)/2;
            }
        }
        cout << ans1 << " " << ans2 << endl;
        for(int i=0; i<=n; i++)
        {
            g[i].clear();
        }
    }
    return 0;
}