记录编号	436058	评测结果	AAAAAAAAAA
题目名称	[HNOI 2012] 矿场搭建	最终得分	100
用户昵称	Hzoi_Ivan	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2017-08-10 21:44:38	内存使用	0.36 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define N 1500
using 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(){
    freopen("bzoj_2730.in","r",stdin);
    freopen("bzoj_2730.out","w",stdout);
	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;
}
/*
5
1 2
2 3
1 3
3 4
1 4
*/