矿场搭建
根据题意，发生事故时会有一个挖煤点坍塌，
只有当这个点是割点，会对图的连通性产生影响，
我们首先Tarjan一遍找到所有割点，将原图除去这些割点后，
遍历一遍，找出所有连通块，分三种情况讨论：
1、该连通块连接着两个及以上的割点，这时如果有一个割点被摧毁，
还可以从另一个割点到达其他连通块，不需要建逃生通道
2、该连通块连接着一个割点，若这个割点被摧毁，该连通块的人就无法逃生，
必须建一个出口（从该连通块的所有节点中选一个，ans*=size）
3、该连通块没有割点相连，要建两个出口，如果其中一个被摧毁，还可以从另一个逃出去
ans*=C(size,2);
1 #include<algorithm> 2 #include<cstdio> 3 #define reset(a) std::fill(a,a+1+n,0) 4 #define min(a,b) ((a)<(b)?(a):(b)) 5 #define max(a,b) ((a)>(b)?(a):(b)) 6 #define N 50020 7 int n,m,dfn[N],low[N],vis[N],tot,k,T; 8 const int ch_top=4e7+3; 9 char ch[ch_top],*now_r=ch-1,*now_w=ch-1; 10 inline int read(){ 11 while(*++now_r<'0'); 12 register int x=*now_r-'0'; 13 while(*++now_r>='0')x=x*10+*now_r-'0'; 14 return x; 15 } 16 long long ans; 17 bool gd[N]; 18 int Head[N],to[N<<1],next[N<<1],num; 19 void Tarjan(int u){ 20 dfn[u]=low[u]=++tot; 21 int cnt=0; 22 for(int i=Head[u];i;i=next[i]){ 23 int v=to[i]; 24 if(!dfn[v]){ 25 Tarjan(v); cnt++; 26 low[u]=min(low[u],low[v]); 27 if((u==1&&cnt>1)||(u!=1&&low[v]>=dfn[u])) 28 gd[u]=1; 29 } 30 else low[u]=min(low[u],dfn[v]); 31 } 32 } 33 int dfs(int t){ 34 int sz=1; vis[t]=1; 35 for(int i=Head[t];i;i=next[i]) 36 if(!vis[to[i]]&&!gd[to[i]]) 37 sz+=dfs(to[i]); 38 else if(vis[to[i]]!=T&&gd[to[i]]){ 39 k++; vis[to[i]]=T; 40 } 41 return sz; 42 } 43 int main() 44 { 45 fread(ch,1,ch_top,stdin); 46 int now=0; 47 m=read(); 48 while(m){ 49 if(!m) break; 50 reset(Head); reset(gd); 51 reset(vis); reset(dfn); 52 num=tot=n=T=0; 53 int x,y; 54 for(int i=1;i<=m;i++){ 55 x=read(); y=read(); 56 to[++num]=y; 57 next[num]=Head[x]; 58 Head[x]=num; 59 to[++num]=x; 60 next[num]=Head[y]; 61 Head[y]=num; 62 n=max(n,max(x,y)); 63 } 64 int cnt=0; 65 Tarjan(1);ans=1; 66 for(int i=1;i<=n;i++) 67 if(!gd[i]&&!vis[i]){ 68 k=0; T++; 69 int size=dfs(i); 70 if(k==0) ans*=(long long)size*(size-1)/2,cnt+=2; 71 else if(k==1) ans*=size,cnt++; 72 } 73 printf("Case %d: %d %lld ",++now,cnt,ans); 74 m=read(); 75 } 76 return 0; 77 }
双倍经验：UVA1108