la5135 无向图 点-双连通 运用

大白书 P314

#include <iostream>

#include <algorithm>

#include <string.h>

#include <stack>

#include <vector>

#include <cstdio>

#include <map>

using namespace std;

typedef long long LL;

struct Edge{int u,v; };

const int maxn = +;

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

vector<int> G[maxn],bcc[maxn];

stack<Edge> S;

int dfs(int u, int fa){

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

      int child=;

      for(int i=; i<G[u].size(); ++i){

          int v=G[u][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;

}

struct ID {

  map<int, int> m;

  int cnt;

  ID():cnt() { }

  int get(int x) {

    if(!m.count(x)) m[x] = cnt++;

    return m[x];

  }

};

int main()

{

      int kase = , n;

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

           memset(pre,,sizeof(pre));

           memset(iscut,,sizeof(iscut));

           memset(bccno,,sizeof(bccno));

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

             G[i].clear();

           dfs_clock = bcc_cnt =  ;

           ID id;

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

             int u,v;

             scanf("%d%d",&u,&v);

             u=id.get(u); v= id.get(v);

             G[u].push_back(v); G[v].push_back(u);

           }

           dfs(,-);

           LL ans1 = , ans2 =;

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

               int cut_cnt  = ;

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

                 if(iscut[bcc[i][j]]) cut_cnt++;

               if(cut_cnt == ){

                    ans1++ ; ans2*= (long long )(bcc[i].size() - cut_cnt);

               }

           }

           if(bcc_cnt==){

             ans1=; ans2 = bcc[].size() *( bcc[].size() - )/;

           }

           printf("Case %d: %lld %lld\n",++kase, ans1, ans2);

      }

    return ;

}