传送门

图的连通性相关的必和割点割边之类的有关。

题目要求对于一个无向图，任意一点被删除后，所有点都和某些指定点是联通的。

这道题比较简单的做法就是求出来所有的块。对于一个块，如果块里有两个及两个以上的割点，那么这个块是不需要钦定点的。两个一下的需要分类讨论。

对于只有一个割点的，肯定要钦定一个点，不然割点挂了整个块就GG了。

对于不存在割点的，要钦定一个点和一个备胎点，免得钦定的点被炸了。

求方案数可以用乘法原理。同样，存在两个及两个以上割点的块不需要考虑，一个和不存在的需要分类讨论。

对于只有一个割点的块，可以挑选的点有$size-1$个。

对于一个割点都没有的块，可以挑选的点有$size \times (size-1)$个。

累乘起来就行了。

//BZOJ 2730//by Cydiater//2016.11.1#include <iostream>#include <cstdlib>#include <queue>#include <map>#include <ctime>#include <cmath>#include <cstring>#include <string>#include <algorithm>#include <cstdio>#include <bitset>#include <set>#include <iomanip>using namespace std;#define ll long long#define up(i,j,n)		for(int i=j;i<=n;i++)#define down(i,j,n)		for(int i=j;i>=n;i--)#define cmax(a,b) a=max(a,b)#define cmin(a,b) a=min(a,b)#define Auto(i,node)		for(int i=LINK[node];i;i=e[i].next)const int MAXN=1e5+5;const int oo=0x3f3f3f3f;inline int read(){	char ch=getchar();int x=0,f=1;	while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}	while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}	return x*f;}int N,M,LINK[MAXN],len=0,dfn[MAXN],low[MAXN],dfs_clock=0,color_num=0,color[MAXN],casenum=0;bool iscut[MAXN],vis[MAXN];ll ans1,ans2,siz,cutnum;struct edge{	int y,next;}e[MAXN];namespace solution{	inline void insert(int x,int y){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;}	inline void Insert(int x,int y){insert(x,y);insert(y,x);}	void tarjan(int node,int father){		dfn[node]=low[node]=++dfs_clock;		int child=0;		Auto(i,node)if(e[i].y!=father){			if(!dfn[e[i].y]){				tarjan(e[i].y,node);child++;				cmin(low[node],low[e[i].y]);				if(low[e[i].y]>=dfn[node])iscut[node]=1;			}else cmin(low[node],dfn[e[i].y]);		}		if(father==0&&child==1)iscut[node]=0;	}	void dfs(int node){		color[node]=color_num;if(iscut[node])return;siz++;		Auto(i,node){			if(iscut[e[i].y]&&color[e[i].y]!=color_num){				cutnum++;color[e[i].y]=color_num;			}			if(!color[e[i].y])dfs(e[i].y);		}	}	void slove(){		N=len=dfs_clock=0;		memset(LINK,0,sizeof(LINK));		memset(iscut,0,sizeof(iscut));		up(i,1,M){int x=read(),y=read();cmax(N,max(x,y));Insert(x,y);}		memset(dfn,0,sizeof(dfn));		up(i,1,N)if(!dfn[i])tarjan(i,0);		memset(color,0,sizeof(color));		color_num=0;ans1=0;ans2=1;		up(i,1,N)if(!iscut[i]&&!color[i]){			color_num++;siz=cutnum=0;dfs(i);			if(cutnum==0){ans1+=2;ans2*=(ll)siz*(ll)(siz-1)/2;}			if(cutnum==1){ans1++;ans2*=(ll)siz;}		}		printf("Case %d: %lld %lld\n",++casenum,ans1,ans2);	}}int main(){	//freopen("input.in","r",stdin);	using namespace solution;	while(scanf("%d",&M)!=EOF)if(M!=0)slove();	return 0;}

BZOJ2730: [HNOI2012]矿场搭建