bzoj2730

题意：
        煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。

输入：
        输入文件有若干组数据，每组数据的第一行是一个正整数 N（N≤500），表示工地的隧道数，接下来的 N 行每行是用空格隔开的两个整数 S 和 T，表示挖 S 与挖煤点 T 由隧道直接连接。输入数据以 0 结尾。

对点双联通分支割点个数分类讨论,
分枝上共计一个点：忽略
没有割点：建立两个出口
一个割点：建立一个出口
其余：不建出口

#include<iostream>
#include<cstdio>

using namespace std;

struct Graph{
    static const int maxn=1e5+5, maxm=3e5+5;
    struct star{int v,nex;}edge[maxm<<1];
    int head[maxn],cnt,n;
    void ini(int n){
        this->n=n; cnt=-1;
        for(int i=0;i<=n;i++) head[i]=-1;
    }
    void add_edge(int u,int v){
        edge[++cnt]=star{v,head[u]}; head[u]=cnt;
        edge[++cnt]=star{u,head[v]}; head[v]=cnt;
    }
}tree;

struct Tarjan:Graph{//割点
    int low[maxn],dfn[maxn],stk[maxn],cut[maxn];
    int step;
    void tarjan(){
        step=0;
        for(int i=0;i<=n;i++) dfn[i]=cut[i]=0;
        for(int i=1;i<=n;i++) if(dfn[i]==0) tarjan(i,0);//多个联通快
    }
    void tarjan(int u,int father=0){//此函数不开放
        low[u]=dfn[u]=++step; stk[++stk[0]]=u;
        int first=1, son=0;
        for(int i=head[u];~i;i=edge[i].nex){
            int v=edge[i].v;
            if(v==father&&!first) first=false;
            else if(dfn[v]) low[u]=min(low[u],dfn[v]);
            else{
                son++;
                tarjan(v,u);
                low[u]=min(low[u],low[v]);
                //一个顶点u是割点,当且仅当1或2
                //1.u为树根且u有多与一个子树
                //2.u不为树根且存在边(u,v)为树边，使得dfn[u]<=low[v]
                if(father!=0&&dfn[u]<=low[v]) cut[u]=1;
                if(father==0&&son>1) cut[u]=1;
            }
        }
        stk[0]--;
    }
    long long nums,cutnums,ans1,ans2;
    void solve(int Case){
        tarjan();
        ans1=0,ans2=1;
        for(int i=1;i<=n;i++) dfn[i]=0;
        for(int i=1;i<=n;i++) {
            if(!cut[i]&&dfn[i]==0) {
                nums=cutnums=0;
                dfs(i,i);
                if(nums==1);//do nothing
                else{
                    if(cutnums>=2) ;//do nothing
                    else if(cutnums==1){
                        ans1++;
                        ans2*=nums-1;
                    }
                    else{
                        ans1+=2;
                        ans2*=(nums-1)*nums/2;
                    }
                }
            }
        }
        cout<<"Case "<<Case<<": "<<ans1<<" "<<ans2<<endl;//输出结果 
    }
    void dfs(int u,int color){
        nums++;
        cutnums+=cut[u];
        dfn[u]=color;
        if(cut[u]) return;
        for(int i=head[u];~i;i=edge[i].nex){
            int v=edge[i].v;
            if(dfn[v]!=color) dfs(v,color);
        }
    }
}graph;

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

int main(){
    int t=0;
    while(true){
        int m=read(),n=0;
        if(m==0) break;
        graph.ini(1000);
        for(int i=0;i<m;i++) {
            int u=read(),v=read();
            graph.add_edge(u,v);
            n=max(u,n);
            n=max(v,n);
        }
        graph.n=n;
        graph.solve(++t);

    }
}