如果只有一个点双，答案为2，随便选两个点。 否则求每个点双里有几个割点，如果割点个数大于等于2，那么这个点双中不用选点，如果个数为1，那么点双中需要选一个不是割点的点。
#include <bits/stdc++.h> using namespace std; #define N 510 #define ll long long int m,tot,cnt,cr,top,ans,Case,scc; int head[N],nex[N<<1],to[N<<1]; int dfn[N],low[N],iscut[N],st[N]; vector<int>vec[N]; ll num; void init() { tot=0;cnt=0;scc=0;cr=0;top=0;ans=0;num=1; memset(head,0,sizeof(head)); memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(iscut,0,sizeof(iscut)); } void add(int x,int y) { tot++; nex[tot]=head[x];head[x]=tot; to[tot]=y; } void tarjan(int x,int y) { dfn[x]=low[x]=++cnt;st[++top]=x; for(int i=head[x];i;i=nex[i]) if(to[i]!=y) { if(!dfn[to[i]]) { int beg=top;tarjan(to[i],x); low[x]=min(low[x],low[to[i]]); if(low[to[i]]>=dfn[x]) { vec[++scc].clear(); if(x==1)cr++; else iscut[x]=1; while(top!=beg)vec[scc].push_back(st[top--]); vec[scc].push_back(x); } } else low[x]=min(low[x],dfn[to[i]]); } } int main() { //freopen("tt.in","r",stdin); while(scanf("%d",&m)&&m) { init(); for(int i=1,x,y;i<=m;i++) { scanf("%d%d",&x,&y); add(x,y);add(y,x); } tarjan(1,0); iscut[1]=(cr>=2); for(int i=1;i<=scc;i++) { int sz=vec[i].size(),du=0; for(int j=0;j<sz;j++) if(iscut[vec[i][j]])du++; if(du==0)ans+=2,num*=sz*(sz-1)/2; if(du==1)ans++,num*=sz-1; } printf("Case %d: %d %lld\n",++Case,ans,num); } return 0; }