【LA5135 训练指南】井下矿工 【双连通分量】

题意

有一座地下稀有金属矿由n条隧道和一些连接点组成，其中每条隧道连接两个连接点。任意两个连接点之间最多只有一条隧道。为了降低矿工的危险，你的任务是在一些连接点处安装太平井和相应的逃生装置，使得不管哪个连接点倒塌，不在此连接点的多有矿工都能到达太平井逃生。为节约成本，你应当在尽量少的连接点安装太平井。还需要计算出当太平井的数目最小时的安装方案总数。

分析

1对于一个双连通分量，如果它有两个以上的割顶，则不需要建太平井。如果只有一个割顶，则任选一个非割顶的点建太平井。

2若整个图无割顶，则任涂两个点，方案数为n*（n-1）/2

3对于不属于双连通分量的点，只能在他们每个点都建一个太平井

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #include <stack>

 #include <vector>

 using namespace std;

 const int maxn=+;

 int n,sz,N;

 int head[maxn],Next[maxn],to[maxn];

 struct Edge{

     int u,v;

 };

 void add_edge(int a,int b){

     ++sz;

     to[sz]=b;Next[sz]=head[a];head[a]=sz;

 }

 int ansn;

 long long anss;

 int pre[maxn],iscut[maxn],bccno[maxn],dfs_clock,bcc_cnt;

 vector<int>bcc[maxn];

 stack<Edge>S;

 int dfs(int u,int fa){

     int lowu=pre[u]=++dfs_clock;

     int child=;

     for(int i=head[u];i!=-;i=Next[i]){

         int v=to[i];

         Edge e=(Edge){u,v};

         if(!pre[v]){

             S.push(e);

             child++;

             int lowv=dfs(v,u);

             lowu=min(lowu,lowv);

             if(lowv>=pre[u]){

                 iscut[u]=;

                 bcc_cnt++;bcc[bcc_cnt].clear();

                 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(pre[v]<pre[u]&&v!=fa){

             S.push(e);

             lowu=min(lowu,pre[v]);

         }

     }

     if(fa<&&child==)iscut[u]=;

     return lowu;

 }

 void find_bcc(int n){

     memset(pre,,sizeof(pre));

     memset(iscut,,sizeof(iscut));

     memset(bccno,,sizeof(bccno));

     dfs_clock=bcc_cnt=;

     for(int i=;i<=n;i++)

         if(!pre[i])dfs(i,-);

 }

 int kase;

 int main(){

     kase=;

     while(scanf("%d",&n)!=EOF&&n){

         int a,b;

         sz=;

         memset(head,-,sizeof(head));

         N=;

         ansn=;

         anss=;

         for(int i=;i<=n;i++){

             scanf("%d%d",&a,&b);

             N=max(N,a);

             N=max(N,b);

             add_edge(a,b);

             add_edge(b,a);

         }

         find_bcc(N);

         for(int i=;i<=bcc_cnt;i++){

             int num=;

             for(int j=;j<bcc[i].size();j++){

                 if(iscut[bcc[i][j]])

                     num++;

             }

             if(num==){

                 ansn++;

                 anss*=(long long)(bcc[i].size()-);

             }

             if(num==){

                 ansn+=;

                 anss*=(long long)bcc[i].size()*(long long)(bcc[i].size()-)/;

             }

         }

         for(int i=;i<=N;i++){

             if(!bccno[i])

                 ansn++;

         }

         ++kase;

         printf("Case %d: ",kase);

         printf("%d %lld\n",ansn,anss);

     }

 return ;

 }