对于一个点双联通分量，如果它连接了两个或更多割点
那么不论哪个点GG都有至少一条路通到其他的点双联通分量，所以我们不用考虑
如果它只连接一个割点，如果这个割点GG，那整个块也一起GG，所以要再这个块里建一个出口
如果它没有连接割点，只建一个出口还不够，可能这个出口所在的点GG，所以要两个出口
那么三种情况的各自的方案数分别为
1 (啥都不干)
块内点的大小 (块内的每个点都可以建出口)
$C_{块内点的大小}^2$ (块内顺便选两个点建出口)
根据乘法原理把每个块的方案数乘起来就是总方案数了
然后Tarjan求出所有割点和点双联通分量就好了
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<vector> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=1e4+7; int fir[N],from[N<<1],to[N<<1],cntt; inline void add(int &a,int &b) { from[++cntt]=fir[a]; fir[a]=cntt; to[cntt]=b; } int dfs_clock,dfn[N],low[N],st[N],Top,cut[N],rt,tot; vector <int> be[N];//be[i][j]存属于第i个块的第j个点 void Tarjan(int x)//Tarjan模板求割点 { dfn[x]=low[x]=++dfs_clock; st[++Top]=x; int ch=0; for(int i=fir[x];i;i=from[i]) { int &v=to[i]; if(!dfn[v]) { Tarjan(v); ch++; low[x]=min(low[x],low[v]); if((x==rt&&ch>1)||(x!=rt&&dfn[x]<=low[v])) cut[x]=1;//注意节点为根时要特判 if(dfn[x]<=low[v]) { be[++tot].clear();//注意多组数据 while(st[Top]!=v) be[tot].push_back(st[Top--]); be[tot].push_back(st[Top--]); be[tot].push_back(x);//把割点也算进相邻的点双，方便统计 } } else low[x]=min(low[x],dfn[v]); } } int n,m; ll ans1,ans2; int main() { int a,b,num=0; while(scanf("%d",&m)&&m) { memset(cut,0,sizeof(cut)); memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(fir,0,sizeof(fir)); n=tot=dfs_clock=Top=cntt=ans1=0; ans2=1;//初始化 for(int i=1;i<=m;i++) { a=read(); b=read(); add(a,b); add(b,a); n=max(n,max(a,b));//节点数还要自己求 } for(int i=1;i<=n;i++) if(!dfn[i]) rt=i,Tarjan(i); for(int i=1;i<=tot;i++) { int len=be[i].size(),cnt=0; for(int j=0;j<len;j++) cnt+=cut[be[i][j]];//记录割点个数 if(!cnt)//如果没割点 ans1+=2,ans2*=((1ll*len*(len-1))>>1); else if(cnt==1) ans1++,ans2*=(len-1);//注意len-1,因为len包括一个割点 } printf("Case %d: %lld %lld ",++num,ans1,ans2); } return 0; }