Uva(1108)(Mining Your Own Busine

链接：https://vjudge.net/problem/UVA-1108
思路：还是熟悉模板的练习题，但是要先建模，首先不可能在割顶放，因为这样割顶没了剩下的连通块都没了，所以肯定不是最优，其次如果有两个割顶，那么此时一定连着两边，所以这里可以不用放，所以只有一个割顶的连通块才需要放。且可以放在任意非割顶的位置，所以方案数就是每个要放的连通块的非割顶点数相乘即可，注意如果整个图只有一个割顶，那么需要放两个，这种情况需要特判！！！！
补充：这是求的点双连通分量，如果只有两个点一条边其实也是算点双连通分量的。。。。且两个点都算作割顶
代码：

#include<cstdio>
#include<deque>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;

const int maxn = 5*1e4+10;
vector<int> G[maxn],bbc[maxn];
int bbcno[maxn];
int dfn[maxn],low[maxn];
int iscut[maxn];
int ntime,bbc_cnt;
int m;

struct edge{
    int u,v;
    edge(){}
    edge(int uu,int vv):u(uu),v(vv){};
};

deque<edge> edges;

void tarjan(int u,int f){
    dfn[u] = low[u] = ++ntime;
    int child = 0;
    for(int i=0;i<G[u].size();i++){
        int v = G[u][i];
        if(!dfn[v]){
            edges.push_back(edge(u,v));
            child++;
            tarjan(v,u);
            low[u] = min(low[u],low[v]);
            edge tmp;
            if(dfn[u]<=low[v]){
                iscut[u] = 1;
                bbc_cnt++;
                bbc[bbc_cnt].clear();
                do{
                tmp = edges.back();
                edges.pop_back();
                if(bbcno[tmp.u]!=bbc_cnt){
                    bbc[bbc_cnt].push_back(tmp.u);
                    bbcno[tmp.u] = bbc_cnt;
                } 
                if(bbcno[tmp.v]!=bbc_cnt){
                    bbc[bbc_cnt].push_back(tmp.v);
                    bbcno[tmp.v] = bbc_cnt;
                }
            }while(!(tmp.u==u&&tmp.v==v));
            }
        }
        else if(dfn[v]<dfn[u]&&v!=f){
            edges.push_back(edge(u,v));
            low[u] = min(low[u],dfn[v]);
        }
    }
    if(f<0&&child==1)iscut[u] = 0;
}

void find_bbc(int n){
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(bbcno,0,sizeof(bbcno));
memset(iscut,0,sizeof(iscut));
ntime = bbc_cnt = 0;
for(int i=0;i<n;i++){
    if(!dfn[i])tarjan(i,-1);
}
}

int main(){
    int kase = 0;
    while(scanf("%d",&m)&&m){
        int maxnn = 0;
        for(int i=0;i<maxn;i++)G[i].clear();
        for(int i=0;i<m;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            maxnn = max(maxnn,a);
            maxnn = max(maxnn,b);
            a--;
            b--;
            G[a].push_back(b);
            G[b].push_back(a);
        }
        find_bbc(maxnn);
        long long ans1 = 0,ans2 = 1;
        for(int i=1;i<=bbc_cnt;i++){
            int cut_bbc = 0;
            for(int j=0;j<bbc[i].size();j++){
                if(iscut[bbc[i][j]]){
                    printf("%d\n",bbc[i][j]);
                    cut_bbc++;
                }
            }
            if(cut_bbc==1){
                ans1++;
                ans2*=(long long)(bbc[i].size()-cut_bbc);
            }
        }
        if(bbc_cnt==1){
            ans1 = 2;
            ans2 = bbc[1].size()*(bbc[1].size()-1)/2;
        }
        printf("Case %d: %lld %lld\n",++kase,ans1,ans2);
    }
    return 0;
}