这道题既然说的是有一个矿点崩塌……那么也就是在图中去掉这个点和这个点所连的所有边，那也就是割点了。
那我们先手把图建出来之后把图中所有的割点都跑出来，这样图中会剩下一堆联通块。之后我们考虑一下对于每个联通块必须建立的逃生点个数。
如果一个联通块不与任意一个割点相连，那么我们需要在里面建两个逃生点（因为有可能只建一个逃生点的话那个点塌了就凉凉），也就是有C（n，2）种搭建的方法。
如果只于一个割点相连，那么建立一个逃生点即可（防止那个割点坍塌），一共有块的大小的搭建方法。
如果与两个或以上割点相连，那么我们不需要进行任何操作，因为只会有一个点发生坍塌，即使一个割点坍塌还可以从另一个跑出去。、
这样就完事了……然后要记住每次都要把答案清空……dfs的时候不要写错。注意在统计一个块所连的割点个数的时候要注意不要跑重，可以选择跑一次打一次标记再清除这么个方法。
然后这题挺坑的就是不告诉你最多有多少个点……虽然说好像和边数相近……但是这样很吓人。还有就是似乎数据略水……我tarjan一开始传错参都能70pts……
看一下代码。
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> #include<queue> #include<set> #include<map> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') using namespace std; typedef long long ll; const int M = 10005; const int INF = 2000000009; int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } struct edge { int next,to,from; }e[M<<1]; int n,m,head[M],ecnt,low[M],dfn[M],x,y,idx,tot,maxnode,cnt,q[M],curr; bool vis[M],cut[M]; ll ans1,ans2,sz; int C(int x) { if(x == 1) return 1; else return x * (x-1) / 2; } void add(int x,int y) { e[++ecnt].to = y; e[ecnt].next = head[x]; head[x] = ecnt; } void clear() { memset(e,0,sizeof(e)); memset(vis,0,sizeof(vis)); memset(cut,0,sizeof(cut)); memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); ecnt = maxnode = idx = 0; memset(head,0,sizeof(head)); ans1 = 0,ans2 = 1,cnt++; } void tarjan(int x,int fa) { low[x] = dfn[x] = ++idx; int child = 0; for(int i = head[x];i;i = e[i].next) { if(!dfn[e[i].to]) { tarjan(e[i].to,fa); low[x] = min(low[x],low[e[i].to]); if(low[e[i].to] >= dfn[x] && x != fa) cut[x] = 1; if(x == fa) child++; } low[x] = min(low[x],dfn[e[i].to]); } if(x == fa && child >= 2) cut[x] = 1; } void dfs(int x,int fa) { //printf("@%d %d ",x,fa); vis[x] = 1,sz++; for(int i = head[x];i;i = e[i].next) { if(e[i].to == fa || vis[e[i].to]) continue; if(cut[e[i].to]) { vis[e[i].to] = 1,tot++; q[++curr] = e[i].to; continue; } dfs(e[i].to,x); } } int main() { while(1) { n = read(); if(!n) break; clear(); rep(i,1,n) x = read(),y = read(),add(x,y),add(y,x),maxnode = max(max(x,y),maxnode); rep(i,1,maxnode) if(!dfn[i]) tarjan(i,i); rep(i,1,maxnode) { tot = 0,sz = 0; if(cut[i] || vis[i]) continue; rep(j,1,curr) q[j] = 0;curr = 0; dfs(i,i); rep(j,1,curr) vis[q[j]] = 0; if(tot == 0) ans2 *= C(sz),ans1 += 2; else if(tot == 1) ans2 *= sz,ans1++; } printf("Case %d: %lld %lld ",cnt,ans1,ans2); } return 0; }