C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 424K, 提交时间: 2022-08-21 12:16:06

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
const int maxn=1e3+6;
struct edge{int to,next;}e[maxn<<1];
int n,m,T,low[maxn],dfn[maxn],top,que[maxn<<2],last[maxn],tim,cnt,cas,deg,tot,num,vis[maxn],ans1,root;
bool cut[maxn],inque[maxn];ll ans2;
void insert(int u,int v){
    e[++cnt]=(edge){v,last[u]};last[u]=cnt;
    e[++cnt]=(edge){u,last[v]};last[v]=cnt;
}
void tarjan(int x){
    dfn[x]=low[x]=++tim;que[++top]=x;inque[x]=1;
    reg(x){
        if(!dfn[e[i].to]){tarjan(e[i].to);low[x]=min(low[x],low[e[i].to]);}
        else if(inque[e[i].to]){low[x]=min(low[x],dfn[e[i].to]);continue;}
        if(dfn[x]<=low[e[i].to]){if(x==root)deg++;else cut[x]=1;}
    }
}
void dfs(int x){
    vis[x]=T;if(cut[x])return;tot++;
    reg(x){
        if(cut[e[i].to]&&vis[e[i].to]!=T)num++,vis[e[i].to]=T;
        if(!vis[e[i].to])dfs(e[i].to);
    }
}
int main()
{
    while(1){
        cin>>m;if(!m)break;
        mem(e,0);mem(low,0);mem(dfn,0);mem(cut,0);mem(vis,0);mem(inque,0);mem(que,0);mem(last,0);
        cnt=n=tim=T=ans1=top=0,cas++,ans2=1;
        rep(i,1,m){
            int x,y;
            cin>>x>>y;
            insert(x,y);n=max(n,max(x,y));
        }
        rep(i,1,n){
            if(!dfn[i]){tarjan(root=i);if(deg>=2)cut[root]=1;}
            deg=0;
        }
        rep(i,1,n)
            if(!vis[i]&&!cut[i]){
                ++T,tot=num=0,dfs(i);
                if(!num)ans1+=2,ans2*=tot*(tot-1)/2;
                if(num==1)ans1++,ans2*=tot;
            }
        printf("Case %d: %d %lld\n",cas,ans1,ans2);
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 3ms, 内存消耗: 632K, 提交时间: 2020-10-03 12:51:44

#include<bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
using namespace std;
const int N=5e4+5;
struct Edge{int to,nxt;}e[N<<1];
int n,m,fst[N],tote,R,dfn[N],low[N],id;bool cut[N];
void chkmi(int &x,int y){x=x<y?x:y;}
void chkma(int &x,int y){x=x>y?x:y;}
void adde(int u,int v){e[++tote]=(Edge){v,fst[u]};fst[u]=tote;}
void tarjan(int u,int lst){
	dfn[u]=low[u]=++id;
	int totson=0;
	for(int i=fst[u],v;~i;i=e[i].nxt){
		v=e[i].to;
		if(!dfn[v]){
			tarjan(v,i);chkmi(low[u],low[v]);
			if(u!=R&&low[v]>=dfn[u])cut[u]=true;
			if(u==R)totson++;
		}
		if(i!=(lst^1))chkmi(low[u],dfn[v]);
	}
	if(u==R&&totson>=2)cut[u]=true;
}
int bel[N],p,totcut,tot,ans;ULL res;
void dfs(int u){
	bel[u]=tot;p++;
	for(int i=fst[u],v;~i;i=e[i].nxt){
		v=e[i].to;
		if(cut[v]&&bel[v]!=tot)totcut++,bel[v]=tot;
		if(!bel[v])dfs(v);
	}
}
int main(){
	int cas=0;
	scanf("%d",&m);
	while(m){
		cas++;
		memset(fst,-1,sizeof(fst));tote=1;n=0;
		for(int i=1,u,v;i<=m;i++)scanf("%d%d",&u,&v),adde(u,v),adde(v,u),chkma(n,u),chkma(n,v);
		for(int i=1;i<=n;i++)dfn[i]=low[i]=bel[i]=0,cut[i]=false;
		for(int i=1;i<=n;i++)if(!dfn[i])R=i,tarjan(i,0);
		ans=tot=0;res=1;
		for(int i=1;i<=n;i++)if(!bel[i]&&!cut[i]){
			totcut=p=0;tot++;dfs(i);
			if(!totcut)ans+=2,res*=(ULL)p*(p-1)/2;
			else if(totcut==1)ans++,res*=(ULL)p;
		}
		printf("Case %d: %d %llu\n",cas,ans,res);
		scanf("%d",&m);
	}
	return 0;
}