LA 5135 Mining Your Own Business(割点とBCCを求める)

n個の点、m個の辺、できるだけ少ない点を太平井戸として選んで、いずれかの点を削除させて、残りの頂点はすべて太平井戸までの経路があります.設置する必要がある最小限の太平井戸の数と、対応する案数を聞く.
モデル:任意の点を削除した後、各連通成分に少なくとも1つの黒点があるように、図中にできるだけ少ない点に黒塗り(太平井戸)を選択しない.
解析の結果、点−二重連通成分における割点の数が1の場合、残りのいずれかの非割点の頂点を選択して黒く塗ればよいことが分かった.図全体に割点がない場合は、任意に2つの点を選択して黒く塗ってください.

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define maxn 50005
struct Edge
{
    int u,v;
};
int dfn[maxn],iscut[maxn],bccno[maxn],dfs_clock,bcc_cnt;
vector<int> G[maxn],bcc[maxn];
stack<Edge> S;


int dfs(int u,int fa) //u dfs       fa。
{
    int lowu=dfn[u]=++dfs_clock,child=0;
    for(int i=0; i<G[u].size(); ++i)
    {
        int v=G[u][i];
        Edge e=(Edge)
        {
            u,v
        };
        if(!dfn[v]) //     v
        {
            S.push(e);
            ++child;
            int lowv=dfs(v,u);
            lowu=min(lowu,lowv);//    low      
            if(lowv>=dfn[u])
            {
                iscut[u]=1;
                bcc_cnt++;
                bcc[bcc_cnt].clear();//bcc 1    ！！！！！
                for(;;)
                {
                    Edge x=S.top();
                    S.pop();
                    if(bccno[x.u]!=bcc_cnt)
                    {
                        bcc[bcc_cnt].push_back(x.u);
                        bccno[x.u]=bcc_cnt;
                    }
                    if(bccno[x.v]!=bcc_cnt)
                    {
                        bcc[bcc_cnt].push_back(x.v);
                        bccno[x.v]=bcc_cnt;
                    }
                    if(x.u==u&&x.v==v) break;
                }
            }


        }
        else if(dfn[v]<dfn[u]&&v!=fa)   //        
            {
                S.push(e);
                lowu=min(lowu,dfn[v]);
            }
    }
    if(fa<0&&child==1) iscut[u]=0;  //       ！！！！！
    return lowu;
}


void find_bcc(int n){
    memset(dfn,0,sizeof(dfn));
    memset(iscut,0,sizeof(iscut));
    memset(bccno,0,sizeof(bccno));
    dfs_clock=bcc_cnt=0;
    for(int i=0;i<n;++i) if(!dfn[i]) dfs(i,-1);
}




int main()
{
    int ca=1,i,m,n=0,x,y,j;
    while(~scanf("%d",&m)&&m){
        for(i=0;i<maxn;++i) G[i].clear();
        while(m--){
            scanf("%d%d",&x,&y);
            --x,--y;
            G[x].push_back(y);
            G[y].push_back(x);
            n=max(n,max(x,y));
        }
        find_bcc(n);
        LL ans1=0,ans2=1;
        for(i=1;i<=bcc_cnt;++i){
            int cut_cnt=0;
            for(j=0;j<bcc[i].size();++j)
                if(iscut[bcc[i][j]]) ++cut_cnt;
            if(cut_cnt==1) {
                ++ans1;
                ans2*=(LL)(bcc[i].size()-cut_cnt);
            }
        }
        if(bcc_cnt==1) {ans1=2;ans2=(LL)bcc[1].size()*(bcc[1].size()-1)/2;}
        printf("Case %d: %lld %lld
",ca++,ans1,ans2);
    }
    return 0;
}