LA 5135 井下矿工（点—双连通分量模板题）

题意：
在一个无向图上选择尽量少的点涂黑，使得任意删除一个点后，每个连通分量至少有一个黑点。

思路：

首先dfs遍历求出割顶和双连通分量，并把每个连通分量保存下来。

接下来分情况讨论：

如果一个点—双连通分量只有一个割顶，在该分量中必须将一个非割顶涂黑。

如果一个点—双连通分量有2个及以上的割顶，不需要涂黑。

如果整个图没有割顶，则至少需要涂黑两个点。（因为有可能删除的就是涂黑的点）

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<vector>

 #include<stack>

 #include<queue>

 #include<cmath>

 #include<map>

 using namespace std;

 const int maxn=+;

 int m;

 struct Edge

 {

     int u,v;

     Edge(int x,int y):u(x),v(y){}

 };

 stack<Edge> S;

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

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

 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]=true;

                 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(,-);

 }

 int main()

 {

     //freopen("D:\\input.txt","r",stdin);

     int kase=;

     while(~scanf("%d",&m) && m)

     {

         for(int i=;i<maxn;i++)  {G[i].clear();bcc[i].clear();}

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

         {

             int u,v;

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

             G[u].push_back(v);

             G[v].push_back(u);

         }

         find_bcc(m);

         long long 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 ;

 }