POJ 3177 Redundant Paths (POJ 3352)
2010-04-12，阅读题目
2010-04-13，学习算法，然后挂了-_-|||
2010-04-14，代码实现，AC
解题报告：
首先，我们应该学习一些基本概念和算法，参见byvoid神牛的：图的割点、桥与双连通分支。看完以后，直接做就是了。补充两点是：
(1) 这题收缩的双连通分量是边双连通分量；
(2) 不必重新构造收缩边双连通分量后的图，直接在染色的过程统计新图的点的度即可。
poj 3352 Road Construction跟此题一样，还简单一点，直接交过去也可以，我把去重边的部分删了和把数组减小了。
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 | #include <stdio.h> #include <string.h> const int maxn = 5003, maxm = 10003; int n, m, el[maxm][2], et[maxn], *edge[maxn], deep[maxn], low[maxn]; int color[maxn], color_n, degree[maxn], answer; int input() { scanf("%d%d", &n, &m); memset(et, 0, sizeof(et)); for (int i = 1; i <= m; ++i) { scanf("%d %d", &el[i][0], &el[i][1]); ++et[el[i][0]]; ++et[el[i][1]]; } for (int i = 1; i <= n; ++i) edge[i] = new int [et[i] + 1]; memset(et, 0, sizeof(et)); for (int i = 1; i <= m; ++i) { int u = el[i][0], v = el[i][1]; edge[u][et[u]++] = v; edge[v][et[v]++] = u; } return 0; } int dfs(int u, int father, int d) { color[u] = 1; deep[u] = low[u] = d; for (int i = 0, v = edge[u][0]; i < et[u]; v = edge[u][++i]) if (!color[v]) { dfs(v, u, d + 1); low[u] = low[u] < low[v] ? low[u] : low[v]; } else if (v != father) { low[u] = low[u] < deep[v] ? low[u] : deep[v]; } return 0; } int fill_color(int u) { color[u] = color_n; for (int i = 0, v = edge[u][0]; i < et[u]; v = edge[u][++i]) if ((deep[u] + 1 == deep[v] && deep[u] < low[v]) || (deep[v] + 1 == deep[u] && deep[v] < low[u])) { if (color[v]) { ++degree[color_n]; ++degree[color[v]]; } } else if (!color[v]) { fill_color(v); } return 0; } int work() { memset(color, 0, sizeof(color)); for (int u = 1, k = 0; u <= n; ++u, k = 0) { for (int i = 0, v = edge[u][0]; i < et[u]; v = edge[u][++i]) if (color[v] < u) { edge[u][k++] = v; color[v] = u; } et[u] = k; } memset(color, 0, sizeof(color)); dfs(1, 0, 1); memset(color, 0, sizeof(color)); memset(degree, 0, sizeof(degree)); color_n = answer = 0; for (int i = 1; i <= n; ++i) if (!color[i]) { ++color_n; fill_color(i); } for (int i = 1; i <= color_n; ++i) answer += degree[i] == 1 ? 1 : 0; answer = (answer + 1) >> 1; return 0; } int output() { printf("%d\n", answer); return 0; } int main() { input(); work(); output(); return 0; } |