煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。

很容易的想到如果是割点塌掉的情况。

如果这个割点把整张图分裂了，那么就要保证每块里面都要装一个救援出口。

所以可以 这样做，先求出割点。然后dfs剩下的块。如果一个块只连接到了一个割点，那么这个块里面要有一个救援出口。否则就不用了。

如果没割点的话，要两个出口。不然有可能出口塌了= =。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int p[50010],n1[50010],h[10010],v[10010],dfn[10010],low[10010],b[10010];
int s[50010],c[50010],tmp[50010],m,n,ee,tot,col;long long An1,An2;
void ae(int a,int b){
	p[ee]=b;	n1[ee]=h[a];	h[a]=ee++;
}void dfs(int u){
	v[u]=1;dfn[u]=low[u]=++tot;
	for(int i=h[u];~i;i=n1[i])	if(!v[p[i]]){
		dfs(p[i]);
		low[u]=min(low[u],low[p[i]]);
		if(low[p[i]]>=dfn[u])	b[u]++;
	}else	low[u]=min(low[u],dfn[p[i]]);
}void dfs2(int u){
	v[u]=1,s[col]++;
	for(int i=h[u];~i;i=n1[i])	if(!v[p[i]]){
		if(!b[p[i]])	dfs2(p[i]);
		else	if(c[p[i]]!=col)	c[p[i]]=col,tmp[col]++;
	}
}void init(){
	memset(h,-1,sizeof(h));
	memset(v,0,sizeof(v));
	memset(b,0,sizeof(b));
	memset(v,0,sizeof(v));
	memset(c,0,sizeof(c));
	memset(s,0,sizeof(s));
	memset(tmp,0,sizeof(tmp));
	n=ee=tot=col=An1=0;An2=1;
}int main(){
	int tc=0;
	while(scanf("%d",&m),m){
		int x,y;init();
		for(int i=1;i<=m;i++){
			scanf("%d%d",&x,&y);
			ae(x,y);ae(y,x);
			n=max(n,max(x,y));
		}for(int i=1;i<=n;i++)	if(!v[i]){
			dfs(i);b[i]--;
		}memset(v,0,sizeof(v));
		for(int i=1;i<=n;i++)	if(!v[i]&&!b[i]){
			col++;dfs2(i);
			if(tmp[col]==1)	An1++,An2*=1ll*s[col];
		}if(col==1)	An1=2,An2=1ll*n*(n-1)>>1;
		printf("Case %d: %lld %lld\n",++tc,An1,An2);
	}return 0;
}

• 相关文章