输入文件有若干组数据，每组数据的第一行是一个正整数 N（N≤500），表示工地的隧道数，接下来的 N 行每行是用空格隔开的两个整数 S 和 T，表示挖 S 与挖煤点 T 由隧道直接连接。输入数据以 0 结尾。
输入文件中有多少组数据，输出文件 output.txt 中就有多少行。每行对应一组输入数据的 结果。其中第 i 行以 Case i: 开始（注意大小写，Case 与 i 之间有空格，i 与:之间无空格，: 之后有空格），其后是用空格隔开的两个正整数，第一个正整数表示对于第 i 组输入数据至少需 要设置几个救援出口，第二个正整数表示对于第 i 组输入数据不同最少救援出口的设置方案总 数。输入数据保证答案小于 2^64。输出格式参照以下输入输出样例。
看题之后想一想就应该知道是割点（其实记得几个月前就看过这题，但不会求割点，弃了-_-）
我们会发现啊，割点会把图分成好多连通块
在一个连通块中，如果有两个或以上割点，随便绕个道就OK了，所以不用管
否则必须在其中建一个出口
当整个图是一个连通块时要特判一下
然后一顿乘法原理可以求方案数
#include<cmath> #include<ctime> #include<cstdio> #include<cstring> #include<cstdlib> #include<complex> #include<iostream> #include<algorithm> #include<iomanip> #include<vector> #include<string> #include<queue> #include<set> #include<map> 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<='9'&&ch>='0'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*f; } const int N=500; int n,m,ecnt,last[N],dfn[N],low[N],fa[N],vis[N],cnt,clr,vertex,sz; bool iscut[N]; struct EDGE{int to,nt;}e[N<<2]; inline void readd(int u,int v) {e[++ecnt]=(EDGE){v,last[u]};last[u]=ecnt;} inline void add(int u,int v) {readd(u,v);readd(v,u);} void tarjan(int u) { dfn[u]=low[u]=++cnt;int son=0; for(int i=last[u];i;i=e[i].nt) { if(e[i].to==fa[u])continue; if(!dfn[e[i].to]) { fa[e[i].to]=u;son++;tarjan(e[i].to); low[u]=min(low[u],low[e[i].to]); if(low[e[i].to]>=dfn[u])iscut[u]=1; } else if(dfn[e[i].to]<low[u])low[u]=dfn[e[i].to]; } if(fa[u]==0&&son<=1)iscut[u]=0; } void dfs(int u) { sz++; for(int i=last[u];i;i=e[i].nt) { if(vis[e[i].to]==clr)continue; if(!iscut[e[i].to])vis[e[i].to]=clr,dfs(e[i].to); else vertex++,vis[e[i].to]=clr; } } void initial() { memset(iscut,0,sizeof(iscut));memset(last,0,sizeof(last)); memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));cnt=0; memset(vis,0,sizeof(vis));memset(fa,0,sizeof(fa));clr=0; } int main() { n=read();int T=0; while(n!=0) { int u,v;ll ans=1;int m=0,use=0;ecnt=0; for(int i=1;i<=n;i++)u=read(),v=read(),add(u,v),m=max(m,u),m=max(v,m); for(int i=1;i<=m;i++)if(!dfn[i])tarjan(i); for(int i=1;i<=m;i++)if(!vis[i]&&!iscut[i]) { clr++;vertex=0;sz=0; vis[i]=clr;dfs(i); if(vertex>=2)continue; use++;ans*=sz; } if(use==1)printf("Case %d: 2 %lld\n",++T,(ans*(ans-1))>>1); else printf("Case %d: %d %lld\n",++T,use,ans); n=read();initial(); } return 0; } /* 9 1 3 4 1 3 5 1 2 2 6 1 5 6 3 1 6 3 2 6 1 2 1 3 2 4 2 5 3 6 3 7 0 Case 1: 2 4 Case 2: 4 1 */
