解題區►解題區 - UVa

UVa 1108 - Mining Your Own Business

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

给定一个连通图，设置一个些安全点，使得其他任意一些节点崩塌后，其他点都能到一个安全点，问安全点最小数量和情况数

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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

Sample Output

1
2
Case 1: 2 4
Case 2: 4 1

Solution

先找到所有割點，而一個連通元件上可能連接好幾個割點，對於這個連通元件而言，不論割點是否崩塌，它們仍然可以通到其他連通元件上的逃生口。

如果這個連通元件只有一個割點，則萬一割點崩塌，則連通元件中至少要有一個逃生口，而方法數就是 component.size()，因此會發現，只需要將只有一個割點的連通元件的方法數相乘即可。

對於沒有割點的連通元件而言，至少要設置兩個逃生口，只有一個逃生口會造成萬一逃生口崩塌而死掉的情況，特別考慮方法數 component.size() * (component.size() - 1) / 2。

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
#define MAXN 65536
vector<int> g[MAXN];
int visited[MAXN], vIdx, back[MAXN], depth[MAXN];
int cutPoint[MAXN];
void tarjan(int u, int p, int root) {
	back[u] = depth[u] = ++vIdx;
	visited[u] = 1;
	int son = 0;
	for (int i = 0; i < g[u].size(); i++) {
		int v = g[u][i];
		if (!visited[v]) {
			tarjan(v, u, root);
			back[u] = min(back[u], back[v]);
			son++;
			if ((u == root && son > 1) || (u != root && back[v] >= depth[u]))
				cutPoint[u]++;
		} else if (v != p) {
			back[u] = min(back[u], depth[v]);
		}
	}
}
//
set<int> adjCutPt;
int comSize = 0;
void dfs(int u) {
	visited[u] = 1, comSize++;
	for (int i = 0; i < g[u].size(); i++) {
		int v = g[u][i];
		if (cutPoint[v])	adjCutPt.insert(v);
		if (cutPoint[v] || visited[v])
			continue;
		dfs(v);
	}
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out2.txt", "w+t", stdout); 
	int n, m, x, y;
	int cases = 0;
	while(scanf("%d", &m) == 1 && m) {
		int used[MAXN] = {}, usedn = 0;
		for (int i = 0; i < MAXN; i++)
			g[i].clear();
		n = 0;
		for (int i = 0; i < m; i++) {
			scanf("%d %d", &x, &y);
			n = max(n, max(x, y));
			x--, y--;
			used[x] = used[y] = 1;
			g[x].push_back(y);
			g[y].push_back(x);
		}
		for (int i = 0; i < n; i++)
			usedn += used[i];
		// find all cut point
		vIdx = 0;
		for (int i = 0; i < n; i++)
			visited[i] = cutPoint[i] = 0;
		for (int i = 0; i < n; i++) {
			if (!visited[i] && used[i])
				tarjan(i, -1, i);
		}
//		for (int i = 0; i < n; i++)
//			printf("%d ", cutPoint[i]);
//		puts("");
		// find each component adjacent one cut point, without any cut point.
		vector<int> D; 
		for (int i = 0; i < n; i++)
			visited[i] = 0;
		for (int i = 0; i < n; i++) {
			if (!visited[i] && !cutPoint[i]) {
				comSize = 0, adjCutPt.clear();
				dfs(i);
				if (adjCutPt.size() == 1)
					D.push_back(comSize);
			}
		}
		long long ways = 1, mn = D.size();
		for (int i = 0; i < D.size(); i++)
			ways *= D[i];
		if (D.size() == 0)	ways = (long long) usedn * (usedn-1) / 2, mn = 2;
		printf("Case %d: %lld %lld\n", ++cases, mn, ways);
	}
    return 0;
}
/*
3
1 2
2 3
3 1
32
15 15
8 4
17 7
6 1
12 6
3 17
5 9
20 8
20 4
7 15
4 18
7 17
14 1
14 3
5 3
5 18
13 18
5 15
1 13
18 3
2 4
20 4
20 16
5 20
2 3
10 4
6 6
13 16
2 7
6 17
14 14
1 15
33
10 12
17 14
19 3
2 3
19 9
17 16
9 2
8 9
6 8
14 10
3 13
14 4
9 3
1 18
10 7
15 14
13 1
15 1
16 6
14 20
12 7
6 17
19 5
19 1
10 13
5 3
18 6
12 17
4 5
9 18
9 17
9 20
15 15
*/