Redundant Paths
| Time Limit: 1000MS | Memory Limit: 65536K |
|---|---|
| Total Submissions: 18207 | Accepted: 7554 |
Description
In order to get from one of the F (1 <= F <= 5,000) grazing fields (which are numbered 1..F) to another field, Bessie and the rest of the herd are forced to cross near the Tree of Rotten Apples. The cows are now tired of often being forced to take a particular path and want to build some new paths so that they will always have a choice of at least two separate routes between any pair of fields. They currently have at least one route between each pair of fields and want to have at least two. Of course, they can only travel on Official Paths when they move from one field to another.
Given a description of the current set of R (F-1 <= R <= 10,000) paths that each connect exactly two different fields, determine the minimum number of new paths (each of which connects exactly two fields) that must be built so that there are at least two separate routes between any pair of fields. Routes are considered separate if they use none of the same paths, even if they visit the same intermediate field along the way.
There might already be more than one paths between the same pair of fields, and you may also build a new path that connects the same fields as some other path.
Input
Line 1: Two space-separated integers: F and R
Lines 2..R+1: Each line contains two space-separated integers which are the fields at the endpoints of some path.
Output
Line 1: A single integer that is the number of new paths that must be built.
Sample Input
7 7
1 2
2 3
3 4
2 5
4 5
5 6
5 7Sample Output
2Hint
Explanation of the sample:
One visualization of the paths is:
1 2 3
+---+---+
| |
| |
6 +---+---+ 4
/ 5
/
/
7 +
Building new paths from 1 to 6 and from 4 to 7 satisfies the conditions.
1 2 3
+---+---+
: | |
: | |
6 +---+---+ 4
/ 5 :
/ :
/ :
7 + - - - -
Check some of the routes:
1 – 2: 1 –> 2 and 1 –> 6 –> 5 –> 2
1 – 4: 1 –> 2 –> 3 –> 4 and 1 –> 6 –> 5 –> 4
3 – 7: 3 –> 4 –> 7 and 3 –> 2 –> 5 –> 7
Every pair of fields is, in fact, connected by two routes.
It's possible that adding some other path will also solve the problem (like one from 6 to 7). Adding two paths, however, is the minimum.Source
链接
http://poj.org/problem?id=3177
题意
与POJ3352 Road Construction（Tarjan 求双连通分量缩点）一样，n 个节点 m 条边的无向图，问至少需要添加多少条边使这个图变成边双连通的。但是本题的数据有重边！！！所以需要特别处理一下。
题解
使用 Tarjan 求双连通分量，然后将同一个双连通分量缩点构成成一棵树，统计树上度为 1 的节点的数量 cnt，需要添加边的数量就是 (cnt+1)/2。
两个点之间如果存在有重边，也算是双连通的。
需要一个标记flag， 假如这个点到父亲的路有两条，那么第一条可以不走，但是第二条必须要走，因为是重边，这样儿子节点也就可以更新 low 了。
代码
| Status | Accepted |
|---|---|
| Memory | 312kB |
| Length | 4287 |
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
const int maxn = 5010;
int n, m, tot, cnt, cccnt;
int dfn[maxn], low[maxn], head[maxn], ccno[maxn], ccnum[maxn], degree[maxn];
bool vis[maxn];
struct Edge
{
int to, next;
}edge[20010];
stack <int> S;
void addedge(int u, int v)
{
edge[cnt].to = v;
edge[cnt].next = head[u];
head[u] = cnt++;
}
void init()
{
for (int i = 0; i <= n; ++i)
{
dfn[i] = low[i] = ccno[i] = ccnum[i] = degree[i] = 0;
head[i] = -1;
vis[i] = false;
}
memset(edge, 0, sizeof(edge));
tot = cccnt = 0;
cnt = 1;
}
void tarjan(int u, int father) // 求双连通分量
{
low[u] = dfn[u] = ++tot;
S.push(u);
vis[u] = true;
bool flag = true;
for (int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].to;
if (v == father && flag) // 重边处理，与求桥类似
{
flag = false;
continue;
}
if (!dfn[v])
{
tarjan(v, u);
low[u] = min(low[u], low[v]);
}
else if (vis[v])
low[u] = min(low[u], dfn[v]);
}
if (low[u] == dfn[u]) // 栈中保存的是同一个连通分量
{
cccnt++;
while (1)
{
int v = S.top();
S.pop();
// printf("%d %d\n", cccnt, v);
vis[v] = false;
ccno[v] = cccnt;
ccnum[cccnt]++;
if (v == u)
break;
}
}
}
int main()
{
scanf("%d%d", &n, &m);
init();
int u, v;
for (int i = 0; i < m; ++i)
{
scanf("%d%d", &u, &v);
addedge(u, v);
addedge(v, u);
}
tarjan(1, 0);
for (int i = 1; i <= n; ++i) // 缩点成树求节点的度
{
for (int j = head[i]; j != -1; j = edge[j].next)
{
int v = edge[j].to;
if (ccno[i] != ccno[v])
degree[ccno[i]]++;
}
}
int ans = 0;
for (int i = 1; i <= cccnt; ++i)
{
if (degree[i] == 1) // 找到度为1的节点
ans++;
}
printf("%d\n", (ans+1) / 2); // 至少需要添加的边数
return 0;
}推荐
- pku 3177 (3352) Redundant Paths
- POJ 3177 Redundant Paths（重边标记法，有重边的边双连通分支）
- poj 3177 Redundant Paths(边双连通分量+缩点)
数据
来源于：传送门。
Input for test 1
7 7
1 2
2 3
3 4
2 5
4 5
5 6
5 7
Output for test 1
2
Input for test 2
7 7
1 2
2 3
3 4
2 5
4 5
3 6
5 7
Output for test 2
2
Input for test 3
6 5
3 1
3 2
3 4
3 5
3 6
Output for test 3
3
Input for test 4
10 12
1 2
2 3
3 1
3 4
4 8
4 5
5 6
6 7
7 5
8 9
9 10
10 8
Output for test 4
2
Input for test 5
10 10
1 8
6 3
7 1
3 5
5 2
2 9
9 7
8 4
4 10
10 6
Output for test 5
0
Input for test 6
10 9
1 2
7 4
9 6
10 6
8 4
3 5
3 4
3 6
1 3
Output for test 6
3
Input for test 7
16 22
1 3
7 1
5 1
12 7
6 3
4 7
8 3
10 7
14 6
11 5
9 7
15 4
2 6
13 12
8 2
2 11
6 1
4 11
1 14
3 10
13 16
13 16
Output for test 7
2
Input for test 8
27 35
1 3
10 3
22 3
15 3
11 15
5 15
12 22
18 10
23 11
7 1
2 15
25 1
14 10
24 11
8 2
19 22
4 12
16 4
13 18
9 14
21 13
6 4
17 23
20 17
17 6
3 21
20 3
9 13
17 12
20 18
2 26
26 27
27 8
2 27
26 8
Output for test 8
4
Input for test 9
75 81
1 3
58 3
37 1
36 58
15 36
9 58
10 37
8 1
44 10
33 44
61 8
54 9
4 3
20 44
53 37
26 20
67 54
71 20
5 3
70 54
45 67
14 54
74 67
41 53
52 37
63 53
31 20
55 63
60 55
40 5
75 58
62 31
68 52
72 36
49 9
66 31
43 41
22 52
35 8
21 45
30 15
11 61
7 68
57 30
12 40
27 71
25 40
46 66
42 61
24 37
29 4
59 11
16 74
47 5
69 74
64 59
56 75
19 9
48 56
23 9
13 72
2 43
32 1
73 13
28 7
6 45
18 4
38 42
50 72
17 53
39 50
51 63
34 25
65 64
67 41
58 5
5 27
75 63
7 50
20 18
38 65
Output for test 9
16
Input for test 10
200 250
1 3
106 1
134 1
157 134
23 106
60 134
44 60
117 1
126 1
11 134
139 44
178 3
97 60
101 157
118 44
30 23
128 30
174 3
108 23
110 128
132 157
92 106
173 132
79 106
82 178
7 44
52 79
74 30
4 23
49 7
164 139
127 30
156 4
65 7
120 101
46 97
112 178
8 46
59 60
198 174
100 134
90 92
192 60
125 100
26 178
19 192
63 125
155 126
70 100
35 63
151 126
165 157
146 70
84 157
141 52
160 70
163 8
38 127
171 139
62 101
133 11
177 146
158 125
41 165
145 52
98 30
5 177
68 164
168 173
107 178
86 132
199 127
136 168
71 155
50 128
189 35
193 46
105 70
195 189
89 158
69 177
190 50
28 19
21 92
93 71
170 86
122 21
131 136
197 158
16 108
33 195
18 164
196 141
94 92
61 79
149 26
169 193
124 163
78 189
147 108
150 49
129 70
77 168
194 18
54 100
140 127
24 196
109 158
2 97
17 195
64 28
115 174
185 41
81 141
45 62
180 18
167 109
27 65
123 140
188 77
91 129
73 110
76 173
14 149
103 105
51 11
57 84
58 101
148 193
43 156
162 109
22 61
179 52
67 74
200 117
6 167
119 192
113 41
184 16
32 98
39 160
75 32
175 98
121 78
183 26
47 174
102 79
83 23
172 127
176 74
138 121
182 90
29 156
153 183
114 162
152 47
15 136
12 64
143 155
161 89
99 90
87 114
25 193
144 86
137 64
135 52
56 14
55 112
20 71
142 5
34 126
116 56
40 79
130 89
187 49
85 62
111 136
191 39
166 16
159 120
13 50
95 55
154 33
96 171
181 115
88 21
80 24
48 14
72 21
31 67
9 31
66 143
37 117
104 56
36 86
42 125
186 33
10 184
53 18
164 64
136 63
77 25
128 105
133 147
130 1
67 161
10 132
190 173
195 80
123 1
70 82
126 38
163 7
193 17
152 105
44 24
168 185
174 163
177 40
79 173
70 19
26 60
198 130
97 22
143 67
97 25
119 89
194 163
188 180
49 173
109 71
4 124
58 79
151 178
74 93
34 96
161 65
167 16
172 114
183 14
46 116
199 187
118 175
109 23
101 115
160 114
110 173
96 28
77 182
27 116
Output for test 10
32
Input for test 11
14 16
1 2
1 12
12 2
3 2
4 3
4 5
4 6
6 14
7 14
7 6
7 8
7 9
10 9
11 10
11 13
13 10
Output for test 11
2模板
最后附上邝斌大大的板子。
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
const int MAXN = 5010;//点数
const int MAXM = 20010;//边数，因为是无向图，所以这个值要*2
struct Edge
{
int to,next;
bool cut;//是否是桥标记
}edge[MAXM];
int head[MAXN],tot;
int Low[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN];//Belong数组的值是1~block
int Index,top;
int block;//边双连通块数
bool Instack[MAXN];
int bridge;//桥的数目
void addedge(int u,int v)
{
edge[tot].to = v;edge[tot].next = head[u];edge[tot].cut=false;
head[u] = tot++;
}
void Tarjan(int u,int pre)
{
int v;
Low[u] = DFN[u] = ++Index;
Stack[top++] = u;
Instack[u] = true;
for(int i = head[u];i != -1;i = edge[i].next)
{
v = edge[i].to;
if(v == pre)continue;
if( !DFN[v] )
{
Tarjan(v,u);
if( Low[u] > Low[v] )Low[u] = Low[v];
if(Low[v] > DFN[u])
{
bridge++;
edge[i].cut = true;
edge[i^1].cut = true;
}
}
else if( Instack[v] && Low[u] > DFN[v] )
Low[u] = DFN[v];
}
if(Low[u] == DFN[u])
{
block++;
do
{
v = Stack[--top];
Instack[v] = false;
Belong[v] = block;
}
while( v!=u );
}
}
void init()
{
tot = 0;
memset(head,-1,sizeof(head));
}
int du[MAXN];//缩点后形成树，每个点的度数
void solve(int n)
{
memset(DFN,0,sizeof(DFN));
memset(Instack,false,sizeof(Instack));
Index = top = block = 0;
Tarjan(1,0);
int ans = 0;
memset(du,0,sizeof(du));
for(int i = 1;i <= n;i++)
for(int j = head[i];j != -1;j = edge[j].next)
if(edge[j].cut)
du[Belong[i]]++;
for(int i = 1;i <= block;i++)
if(du[i]==1)
ans++;
//找叶子结点的个数ans,构造边双连通图需要加边(ans+1)/2
printf("%d\n",(ans+1)/2);
}
int main()
{
int n,m;
int u,v;
while(scanf("%d%d",&n,&m)==2)
{
init();
while(m--)
{
scanf("%d%d",&u,&v);
addedge(u,v);
addedge(v,u);
}
solve(n);
}
return 0;
}The end.
2018-07-18 星期三