【HNOI2012, 矿场搭建】割点

题目描述

煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。

于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。

请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。

输入格式

输入文件有若干组数据，每组数据的第一行是一个正整数 N(N≤500) ，表示工地的隧道数，接下来的 N 行每行是用空格隔开的两个整数 S,T(1≤S,T≤1000)，表示挖煤点 S 与挖煤点 T 由隧道直接连接。输入数据以 0 结尾。

对于每组数据，保证输入中出现过的点是连通的。

输出格式

每行对应一组输入数据的结果。其中第 i 行以 Case i: 开始，其后是用空格隔开的两个正整数，第一个正整数表示对于第 i 组输入数据至少需要设置几个救援出口，第二个正整数表示对于第 i 组输入数据不同最少救援出口的设置方案总数。输入数据保证答案小于 264。

样例输入

9
1 3
4 1
3 5
1 2
2 6
1 5
6 3
1 6
3 2
6
1 2
1 3
2 4
2 5
3 6
3 7
0

样例输出

Case 1: 2 4
Case 2: 4 1

提示

Case 1 的四组解分别是 (2,4)，(3,4)，(4,5)，(4,6)；

Case 2 的一组解为 (4,5,6,7)。

思路

因为我们把点双连通分量缩起来以后就成了一棵树，看下图

只有B节点不是叶节点，其他的都是与其所在的双连通分量之外只有一条边的点，就是叶节点，然后我们需要给每个叶节点内部建一个逃生通道，因为如果有一个叶节点里面没有逃生通道的话，那么如果这个叶节点与其他点的唯一的连接点爆了的话那这个叶节点里面的所有点就寄了，所以说一个叶节点里面至少有一个，那么说的话叶节点里面一个安全通道就够了，因为如果这个安全通道不爆，这个叶节点里面的所有节点都可以从这个安全通道里面出去，如果这个安全通道爆了，那么剩下的没爆的点可以穿梭到其他的叶节点逃生，所以就这个思路，个数就是叶节点的个数，方案数就是用乘法原理乘起来，实现方式的话就是在tarjan算法的过程中，如果碰到了一个孩子节点没有返祖边，这个时候更新当前的这个点为割点，然后就是正常更新就行，这个题的输入有点坑，下面请看代码吧：

#include
using namespace std;
const int N = 1010;
vector<int> e[N];
int dfn[N],low[N],n,m,idx,cnt,cut[N];
stack<int> stk;
vector<int> cc[N];
void dfs(int u,int fa){
	dfn[u] = low[u] = ++idx;
	stk.push(u);
	int ch = 0;
	for(auto v : e[u]){
		if(!dfn[v]){
			ch++;
			dfs(v,u);
			low[u] = min(low[u],low[v]);
			if(low[v] >= dfn[u]){	
				++cnt;
				cut[u] = 1;
				cc[cnt].push_back(u);
				while(true){
					int k = stk.top();
					stk.pop();
					cc[cnt].push_back(k);
					if(k == v) break;
				}
			}
		}
		else if(u != fa) low[u] = min(low[u],dfn[v]);
	}
	if(u == 1 && ch <= 1) cut[u] = 0;
}
int main(){
	int _ = 0;
	while(scanf("%d",&m),m){
		idx = cnt = n = 0; 
		while(!stk.empty()) stk.pop();
		for(int i=1;i<=m;i++){
			int a,b;
			scanf("%d%d",&a,&b);
			e[a].push_back(b);
			e[b].push_back(a);
			n = max(max(a,b),n);
		}
		for(int i=1;i<=n;i++) if(!dfn[i]) dfs(i,0);
		printf("Case %d: ",++_);
		if(cnt == 1){
			n = cc[1].size();
			cc[1].clear();
			printf("%d %d\n",2,n*(n-1)/2);
		}
		else{
			int ans1 = 0;
			unsigned long long ans2 = 1;
			for(int i=1;i<=cnt;i++){
				int ncut = 0;
				for(auto x : cc[i]) ncut += cut[x];
				if(ncut == 1){
					ans1 ++;
					ans2 *= cc[i].size()-1;
				}
				cc[i].clear();
			}
			printf("%d %lld\n",ans1,ans2);
		}
		for(int i=1;i<=n;i++) e[i].clear(),low[i] = dfn[i] = cut[i] = 0;
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70