【题目链接】

ybt 1521：【 例 2】矿场搭建
洛谷 P3225 [HNOI2012] 矿场搭建

【题目考点】

1. 图论：割点 点双连通分量

【解题思路】

已知原图是无向连通图。
每个挖煤点是一个顶点，挖煤点坍塌，就相当于删除一个顶点。选择一些顶点作为救援出口。
该题问的是：最少选择几个顶点，可以使得在图中删掉任意顶点后，其余顶点都至少有一条已选择顶点的路径，同时求选择顶点的方案数。

如果该图是一个点双连通图，任何两个顶点之间都至少由2条顶点不重复的路径。那么该图中最少需要选择2个顶点作为救援出口（如果只选一个顶点，那么当该顶点坍塌时，就没有救援出口可以离开了）。选择的方案数为从n个顶点中选择2个顶点的组合数，为$C_n^2$。

如果该图不是点双连通图，那么该图可以分为多个点双连通分量，两个点双连通分量最多有一个共用的割点。因此，可以认为这是由割点连接了多个点双连通分量。

图示：图中每个黑色的圆表示一个点双连通分量，红色的点表示割点。
如果将每个点双连通分量当做一个顶点，每个割点当做一条边，那么通过这种方式可以得到一个树形结构。

其中的叶子结点，也就是度为1的结点，在原图中就是只有一个割点的点双连通分量。
树中如果顶点数大于1，那么度为1的顶点至少有2个。

反证法：假设存在树，其中度为1的顶点只有1个。
树形结构，边数e，顶点数n，满足e=n-1
e条边提供2e个度，也就是图中所有顶点的度加和为2n-2，其中只有一个顶点的度为1，其它n-1个顶点的度数加和为2n-3。
其它每个顶点的度至少为2，因此剩下n-1个顶点的度数加和大于等于2n-2，无法达到2n-3，出现矛盾，命题得证。

对于只有一个割点的点双连通分量（就是树中的“叶子”顶点），该点双连通分量中割点以外的顶点中其中必须设一个出口，否则当割点坍塌时，该点双连通分量中的顶点无法找到一条通往出口的路径。设置出口的方案数为该点双连通分量中非割点顶点数。
对于有两个或两个以上的点双连通分量（就是树中的“分支”顶点），无论哪一个顶点坍塌，该点双连通分量中的顶点都可以通过一条路径走到一个 只有一个割点的点双连通分量（“叶子”顶点）中的出口。因此不需要再这样的点双连通分量中设置出口。
根据乘法原理，设置出口的总方案数为每个只有一个割点的点双连通分量中非割点顶点数的乘积。

【题解代码】

解法1：求割点和点双连通分量，统计各点双连通分量的割点数量

#include <bits/stdc++.h>
using namespace std;
#define N 1005
int dfn[N], low[N], vis[N], ts, vn, root, cutVerNum, verNum, exitNum;
bool cutVer[N];//cutVer[i]：顶点i是否是割点 
vector<int> edge[N], vbc[N];
stack<int> stk;
unsigned long long ans;//出口方案数 
void tarjan(int u)
{
	int t;
	dfn[u] = low[u] = ++ts;
	stk.push(u);
	int child = 0;
	for(int v : edge[u])
	{
		if(dfn[v] == 0)
		{
			tarjan(v);
			low[u] = min(low[u], low[v]);
			if(root == u && ++child > 1 || root != u && dfn[u] <= low[v])
				cutVer[u] = true;
			if(dfn[u] <= low[v])
			{
				vbc[++vn].push_back(u);//点双连通分量编号增加1，先把割点或根u加入点双连通分量 
				do
				{
					t = stk.top();
					stk.pop();
					vbc[vn].push_back(t);
				} while(t != v);//直到v出栈，所有出栈的顶点都属于该点双连通分量 
			}
		}
		else
			low[u] = min(low[u], dfn[v]);
	}
}
int main()
{
	int n, m, u, v, caseNum = 1;
	while(cin >> m && m != 0)//m：隧道数，是边数
	{
		for(int i = 1; i < N; ++i)
		{
			edge[i].clear();
			vbc[i].clear();
		}
		memset(dfn, 0, sizeof(dfn));
		memset(cutVer, 0, sizeof(cutVer));
		ts = n = vn = 0; 
		for(int i = 1; i <= m; ++i)	
		{
			cin >> u >> v;
			edge[u].push_back(v);
			edge[v].push_back(u);
			n = max(n, max(u, v));//n：顶点数。以出现顶点的最大编号作为顶点数 。
		}
		for(int i = 1; i <= n; ++i) if(dfn[i] == 0)
			tarjan(root = i);
		if(vn == 1)//只有1个点双连通分量，那么整个图是点双连通图
		{
			exitNum = 2;//exitNum:出口数
			ans = n*(n-1)/2;//C(n,2) 
		} 
		else
		{
			exitNum = 0;
			ans = 1;//出口方案数 
			for(int i = 1; i <= vn; ++i)
			{
				cutVerNum = 0;
				for(int v : vbc[i]) if(cutVer[v])
					cutVerNum++;
				if(cutVerNum == 1)
				{
					exitNum++;
					ans *= vbc[i].size()-1;//该点双连通分量顶点数为vbc[i].size() 
				}
			}
		}
		cout << "Case " << caseNum++ << ": " << exitNum << ' ' << ans << endl;
	}
	return 0;
}

解法2：求割点后，dfs求点双连通分量，统计割点数量

#include <bits/stdc++.h>
using namespace std;
#define N 1005
int dfn[N], low[N], vis[N], ts, root, cutVerNum, verNum, exitNum;
bool cutVer[N];//cutVer[i]：顶点i是否是割点 
vector<int> edge[N];
unsigned long long ans;//出口方案数 
void tarjan(int u)
{
	dfn[u] = low[u] = ++ts;
	int child = 0;
	for(int v : edge[u])
	{
		if(dfn[v] == 0)
		{
			tarjan(v);
			low[u] = min(low[u], low[v]);
			if(root == u && ++child > 1 || root != u && dfn[u] <= low[v])
				cutVer[u] = true;
		}
		else
			low[u] = min(low[u], dfn[v]);
	}
}
void dfs(int u, int root)
{//每一趟深搜将访问到的顶点标记为root，root是这一趟深搜第一个访问的顶点编号，这样可以访问到上一次已经访问过的割点 
	vis[u] = root;  
	verNum++;//verNum：点双连通分量中的顶点数 
	if(cutVer[u])//到割点后不再访问邻接点 
		cutVerNum++;//cutVerNum：这一趟深搜访问到的割点数量 
	else
	{
		for(int v : edge[u]) if(vis[v] != root)//只要不是这一趟搜索访问到的顶点，都可以访问
			dfs(v, root);
	} 
}
int main()
{
	int n, m, u, v, caseNum = 1;
	while(cin >> m && m != 0)//m：隧道数，是边数
	{
		for(int i = 1; i < N; ++i)
			edge[i].clear();
		memset(dfn, 0, sizeof(dfn));
		memset(cutVer, 0, sizeof(cutVer));
		memset(vis, 0, sizeof(vis)); 
		ts = exitNum = n = 0;//exitNum：出口数 
		ans = 1;//出口方案数 
		for(int i = 1; i <= m; ++i)	
		{
			cin >> u >> v;
			edge[u].push_back(v);
			edge[v].push_back(u);
			n = max(n, max(u, v));//n：顶点数。以出现顶点的最大编号作为顶点数 。
		}
		for(int i = 1; i <= n; ++i) if(dfn[i] == 0)
			tarjan(root = i);
		for(int i = 1; i <= n; ++i) if(vis[i] == 0 && !cutVer[i])//从非割点开始搜索 
		{
			cutVerNum = verNum = 0;//cutVerNum：割点数量 verNum：点双连通分量顶点数 
			dfs(i, i);
			if(cutVerNum == 0)
			{
				exitNum = 2;//exitNum:出口数
				ans = n*(n-1)/2;//C(n,2) 
				break;
			}
			else if(cutVerNum == 1)
			{
				exitNum++;
				ans *=  verNum-1;//点双连通分量中非割点顶点数 
			}
		}
		cout << "Case " << caseNum++ << ": " << exitNum << ' ' << ans << endl;
	}
	return 0;
}