题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2730
首先一遍tarjan找出割点，将图缩点，这些大点中如果有只包含一个割点的，那么如果这个割点被去掉，则这个大点与图不连通，所以这个大点内必须有一个出口；
而如果没有割点，需要建两个出口，以防止一个出口点被去掉；
方案数就是放出口的大点的size乘积；没有割点则方案数为C(m,2)；
注意自己记录点数。
代码如下：
#include<iostream> #include<cstdio> #include<cstring> #include<vector> using namespace std; int const MAXN=505; vector<int>dcc[MAXN]; int t,n,m,siz,tim,ct,head[MAXN],dfn[MAXN],low[MAXN],num,k; long long ans; bool vis1[MAXN],vis2[MAXN],cut[MAXN]; struct N{ int to,next; N(int t=0,int n=0):to(t),next(n) {} }edge[MAXN<<2]; void add(int x,int y) { edge[++ct]=N(y,head[x]);head[x]=ct; edge[++ct]=N(x,head[y]);head[y]=ct; } void tarjan(int x,int f) { dfn[x]=low[x]=++tim; int fl=0; for(int i=head[x],u;i;i=edge[i].next) { if(edge[i].to==f)continue; if(!dfn[u=edge[i].to]) { fl++; tarjan(u,x); low[x]=min(low[x],low[u]); if(low[u]>=dfn[x])/*fl++,*/cut[x]=1; } else low[x]=min(low[x],dfn[u]); } if(!f&&fl==1)cut[x]=0; } int dfs(int x) { int siz=1; vis1[x]=1; for(int i=head[x],u;i;i=edge[i].next) { if(vis1[u=edge[i].to]||vis2[u])continue; if(!cut[u])siz+=dfs(u); // if(!cut[u])siz++,dfs(u); else if(!vis2[u])vis2[u]=1,num++; } return siz; } int main() { while(scanf("%d",&n)==1) { if(!n)return 0; t++;ct=0; tim=0;m=0;// memset(dfn,0,sizeof dfn); memset(low,0,sizeof low); memset(cut,0,sizeof cut); memset(head,0,sizeof head); memset(vis1,0,sizeof vis1); int x,y; for(int i=1;i<=n;i++) { scanf("%d%d",&x,&y); add(x,y); m=max(m,x);m=max(m,y); } for(int i=1;i<=m;i++) if(!dfn[i])tarjan(i,0); ans=1;k=0; for(int i=1;i<=m;i++) if(!vis1[i]&&!cut[i])//不能是割点 { num=0; memset(vis2,0,sizeof vis2); siz=dfs(i); if(num==1)k++,ans*=siz; } if(!k)k=2,ans=(long long)m*(m-1)/2;//m! printf("Case %d: %d %lld ",t,k,ans); } return 0; }