UVALive - 5135(点双联通分量模板)

本文主要是介绍UVALive - 5135(点双联通分量模板)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意:有m条隧道，这些隧道互相交汇(即没有度为0的情况)。现在要建立逃生竖井，使得某些地方塌陷时员工可以从竖井逃生，求最少要建多少逃生竖井，以及建竖井的方案数。

思路:很容易联想到点联通分量的割点，但当割点塌陷时员工就无法逃脱了。所以不能在割点上建，而要在分量上建。当bcc==1时建连两个(以防其中一个塌陷了)，方案数为n(n-1)/2。当bcc不等于1时，考虑在每一个分量上建，如果分量上有2个以及两个以上的割点则不需要建。

#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <algorithm>
#include <functional>
#define inf 0x7fffffff
using namespace std;
typedef long long ll;
const int MAXN=1e5+10;
const int MAX=1e5+10;
const double eps=1e-6;int n,m,Time,bcc;
int low[MAX],dfn[MAX],cut[MAX],belong[MAX];
struct EDGE{int u,v;EDGE(int u,int v):u(u),v(v){}
};
stack<EDGE>q;
vector<int>G[MAX],save[MAX];    //G存图 save存分量void init(){Time=bcc=1;memset(low,0,sizeof(low));memset(dfn,0,sizeof(dfn));memset(cut,0,sizeof(cut));memset(belong,0,sizeof(belong));for(int i=0;i<=n;i++)   G[i].clear(),save[i].clear();while(q.size()) q.pop();    
}void tarjan(int u,int farther){int child=0,v;dfn[u]=low[u]=Time++;for(int i=0;i<G[u].size();i++){int v=G[u][i];EDGE edge(u,v);if(!dfn[v]){q.push(edge);child++;tarjan(v,u);low[u]=min(low[u],low[v]);if(low[v]>=dfn[u]){cut[u]=1;save[bcc].clear();while(1){edge=q.top();q.pop();if(belong[edge.u]!=bcc){    //防止重复save[bcc].push_back(edge.u);belong[edge.u]=bcc;}if(belong[edge.v]!=bcc){    //防止重复save[bcc].push_back(edge.v);belong[edge.v]=bcc;}if(edge.u==u&&edge.v==v){bcc++;break;}}}}else if(dfn[v]<dfn[u]&&v!=farther){EDGE edge(u,v);q.push(edge);low[u]=min(low[u],dfn[v]);}}if(farther<0&&child==1){    //根节点特判cut[u]=0;}
}void get_bcc(){for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i,-1);
}int main(){#ifdef ONLINE_JUDGE#elsefreopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);#endifint flag=1;while(cin>>m){if(m==0)break;n=m*2;init();int u,v;for(int i=1;i<=m;i++){scanf("%d%d",&u,&v);G[u].push_back(v);G[v].push_back(u);n=max(n,max(u,v));}get_bcc();int ansa=0;ll ansb=0;if(bcc-1==1){ansa=2;ansb=(ll)save[1].size()*(save[1].size()-1)/2;  }else{ansb=1;for(int i=1;i<bcc;i++){int cnt=0;for(int j=0;j<save[i].size();j++){if(cut[save[i][j]])cnt++;}if(cnt==1){ansa++;ansb=ansb*(save[i].size()-1);//cout<<save[i].size()-1<<endl;}}}printf("Case %d: %d %lld\n",flag++,ansa,ansb );}return 0;   
}