题目链接：传送门
思路：
如果图是点双联通的，即没有割点，直接从图中随意选两个点即可；
如果有一个割点，删除割点，求连通块的个数即可（在每个连通块内新建一个营救点）。
如果有多个割点，则可以通过其他割点到达，就不用新建营救点。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<stack> #include<queue> using namespace std; typedef long long LL; const int maxn = 1200; int num[maxn],low[maxn],vis[maxn],gedian[maxn],tim,pt,root; vector <int> vc[maxn]; vector <int> block[maxn]; stack <int> st; int MAX(int x,int y) { return x>y?x:y; } int MIN(int x,int y) { return x<y?x:y; } void Init() { memset(vis,0,sizeof(vis)); memset(num,0,sizeof(num)); memset(low,0,sizeof(low)); memset(gedian,0,sizeof(gedian)); for(int i=0;i<maxn;i++) vc[i].clear(),block[i].clear(); tim=0;pt=0; while(!st.empty()) st.pop(); } void Tarjan(int u,int pre) { num[u]=low[u]=++tim; vis[u]=1; st.push(u); int v,i,cnt=0; for(i=0;i<vc[u].size();i++){ v=vc[u][i]; if(!vis[v]){ cnt++; Tarjan(v,u); low[u]=MIN(low[u],low[v]); if((u==root&&cnt>1)||(u!=root&&num[u]<=low[v])) gedian[u]=1; if(num[u]<=low[v]){ pt++; int kk; do{ kk=st.top(); block[pt].push_back(kk); st.pop(); }while(!st.empty()&&kk!=v); block[pt].push_back(u); } } else low[u]=MIN(low[u],num[v]); } } int main(void) { int n,m,x,y,i,j,T=1; while(~scanf("%d",&m)&&m){ Init(); n=0; for(i=1;i<=m;i++){ scanf("%d%d",&x,&y); n=MAX(n,MAX(x,y)); vc[x].push_back(y); vc[y].push_back(x); } for(i=1;i<=n;i++) if(vis[i]==0){ root=i; Tarjan(i,-1); } int art,len; LL ans=0,artnum=1; for(i=1;i<=pt;i++){ art=0;len=block[i].size(); for(j=0;j<len;j++) if(gedian[block[i][j]]) art++; if(art==0) ans+=2,artnum=artnum*len*(len-1)/2; else if(art==1) ans++,artnum=artnum*(len-1); } printf("Case %d: %lld %lld\n",T++,ans,artnum); } return 0; }