tarjan求割点，
每个点双如果不连割点，内部应建两个，连着一个割点，应建一个，连着多个，不用建
#include#include #include #include #include #define N 1500using namespace std;int n,m,cnt,num,tot,ans1,cosmos,bo[N];long long ans2;int dfn[N],low[N],judge[N],top,son,root;int e=1,head[N];struct edge{ int u,v,next;}ed[5000];void add(int u,int v){ ed[e].u=u; ed[e].v=v; ed[e].next=head[u]; head[u]=e++;}void tarjan(int x,int f){ dfn[x]=low[x]=++top; for(int i=head[x];i;i=ed[i].next){ int v=ed[i].v; if(v==x) continue; if(!dfn[v]){ tarjan(v,x); low[x]=min(low[x],low[v]); } else{low[x]=min(low[x],dfn[v]);continue;} if(dfn[x]<=low[v]){ if(x==root)son++; else judge[x]=1; } }}void dfs(int x){ bo[x]=tot; if(judge[x]) return;cnt++; for(int i=head[x];i;i=ed[i].next){ int v=ed[i].v; if(judge[v]&&bo[v]!=tot){num++;bo[v]=tot;} if(!bo[v])dfs(v); }}void init(){ memset(dfn,0,sizeof dfn); memset(low,0,sizeof low); memset(judge,0,sizeof judge); memset(bo,0,sizeof bo); cosmos++; n=0; ans1=0; ans2=1; tot=0; top=0; e=1; memset(head,0,sizeof head);}int main(){ while(scanf("%d",&m)==1&&m!=0){ init(); int u,v; for(int i=1;i<=m;i++){ scanf("%d%d",&u,&v); n=max(n,max(u,v)); add(u,v); add(v,u); } for(int i=1;i<=n;i++){ if(!dfn[i]){ son=0; root=i; tarjan(i,0); if(son>1) judge[i]=1; } } /*for(int i=1;i<=n;i++) printf("%d %d\n",i,judge[i]);*/ for(int i=1;i<=n;i++){ if(!bo[i]&&!judge[i]){ tot++;cnt=num=0; dfs(i); if(!num){ans1+=2;ans2*=cnt*(cnt-1)/2;} if(num==1){ans1++;ans2*=cnt;} //printf("%d %d %d %d\n",i,tot,cnt,num); } } printf("Case %d: %d %lld\n",cosmos,ans1,ans2); } return 0;}