好吧 我是看了yyb大佬的题解才做起的 并且把我的割点模板改得和他的一样
先找割点 然后再一个点一个点地来找连通块 统计该块里的割点数和非割点数
如果没有割点，分类讨论：
1.只有1个节点，只需要建立1个出口，方案累乘不变
2.有n个节点(n≥2)，至少建立两个出口，一个坍塌了走另一个，方案累乘数(n-1)*n/2,由乘法原理得到。
有且仅有1个割点:需要建立一个出口，割点坍塌了走出口，出口坍塌了走割点到达别的连通块
有2个及2个以上个割点:不用建立出口，割点坍塌了1个可以直接到达其他的割点。
#include<iostream> #include<cstdio> #include<queue> #include<cstring> #include<cmath> #include<stack> #include<algorithm> using namespace std; #define ll long long #define rg register #define lson o<<1 #define rson o<<1|1 const int N=500+5,M=500000+5,inf=0x3f3f3f3f,P=19650827; int n,m,cas=0; int bl[N],Bcnt,idx,dfn[N],low[N]; int fcut,cut,book[N]; ll ans1,ans2; template <class t>void rd(t &x){ x=0;int w=0;char ch=0; while(!isdigit(ch)) w|=ch=='-',ch=getchar(); while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); x=w?-x:x; } int head[N],tot=0,root,kid; struct edge{int u,v,nxt;}e[N<<1]; void add(int u,int v){ e[++tot]=(edge){u,v,head[u]};head[u]=tot; } void tarjan(int u,int fa){ dfn[u]=low[u]=++idx; for(int i=head[u],v;i;i=e[i].nxt){ v=e[i].v; if(!dfn[v]){ tarjan(v,u),low[u]=min(low[u],low[v]); if(dfn[u]<=low[v]){ if(u!=root) book[u]=1; else ++kid; } } else if(v!=fa&&low[u]>dfn[v]) low[u]=dfn[v]; } } void dfs(int u){ bl[u]=Bcnt,++fcut; for(int i=head[u],v;i;i=e[i].nxt){ v=e[i].v; if(book[v]&&bl[v]!=Bcnt) ++cut,bl[v]=Bcnt; if(!bl[v]) dfs(v); } } void clean(){ tot=Bcnt=Bcnt=idx=n=0;ans1=0ll,ans2=1ll; for(int i=0;i<=m+1;++i) head[i]=dfn[i]=bl[i]=book[i]=low[i]=0; } int main(){ freopen("in.txt","r",stdin); while(scanf("%d",&m)==1&&m){ clean(); for(int i=1,u,v;i<=m;++i) rd(u),rd(v),add(u,v),add(v,u),n=max(n,max(u,v)); for(int i=1;i<=n;++i) if(!dfn[i]){ kid=0,root=i,tarjan(i,i); if(kid>1) book[i]=1; } for(int i=1;i<=n;++i) if(!bl[i]&&!book[i]){ ++Bcnt,fcut=cut=0; dfs(i); if(!cut){ if(fcut==1) ans1+=1ll; else ans1+=(ll)2,ans2*=(ll)(fcut-1)*fcut/2; } if(cut==1) ans1+=1ll,ans2*=(ll)fcut; } printf("Case %d: ",++cas); printf("%lld %lld ",ans1,ans2); } return 0; }