POJ 2942 Knights of the Round Table
2010-04-15，阅读、分析题目，学习算法，编码实现
2010-04-16，改写部分，调试，AC
好了，如果没有看了下题解，这题我是没啥思路的。
因为之前做了POJ 3177那题，然后也知道这题是双连通分量的，就直接往边双连通分量的方向想。想了半天随手画了个图出来才发现是错的，不是边双连通分量，而是点双连通分量。详细如下：
1. 构造数据给定图的补图，这才是我们所需要的，点代表骑士，边代表两个骑士愿意坐在一起。下面所有的算法都基于此图。
2. 求出图中所有的点双连通分量。对于求图中的双连通分量，还是参考byvoid牛的：图的割点、桥与双连通分支。其中，byvoid牛写到“每找到一条树枝边或后向边(非横叉边)，就把这条边加入栈中”。在我的实现中，由于只需要知道每个双连通分量的点集，所以只记录了树枝边。
还有，请无视黑书（《算法艺术与信息学竞赛》）P287上的解释，私以为那段纯属乱来。那里完全没有分开点双连通和边双连通来讨论，定义是“没有割顶的无向图又称作2-双连通分支，亦称作块”，好了，这里勉强还没有问题。后面又写：“把每个块收缩成一个点”，经过我若干时间的思考，发现边双连通分量是可以收缩的，但是点双连通分量是不可随便收缩的，因为，一个点可以同时属于两个块（点双连通分量），那么，这个点应该收缩到哪里呢？下面那句“它的边就是桥”也是有问题的，理由同上（亏他还加着重号）。这段话如果要重写，我也不知道该怎么写了，因为要多写出很多东西来，大概这样吧：：“无向图的子图中：没有割顶的子图称作点双连通分量，亦称作块。没有桥的子图称作边双连通分量，把每个边双连通分量收缩成一个点，就得到一棵树，它的边就是桥。”这样就没什么问题了。
3. 对每个双连通分量，判断是否存在奇圈（即圈上的点数为奇数）。首先给出两个定理：(1) 若某块存在奇圈，那么该块中的所有点都处于奇圈中；(2) 若某块不可染色为二分图，则该块存在奇圈。(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 | #include <stdio.h> #include <string.h> const int maxn = 1005; int n, m, edge[maxn][maxn], et[maxn], deep[maxn], low[maxn]; int stack[maxn][2], stack_last, bcc[maxn], bcc_n, color[maxn], color_n, answer; bool ee[maxn][maxn], vis[maxn], point[maxn]; bool input() { scanf("%d%d", &n, &m); memset(et, 0, sizeof(et)); memset(ee, 0, sizeof(ee)); for (int i = 1, u, v; i <= m; ++i) { scanf("%d%d", &u, &v); ee[u][v] = ee[v][u] = 1; } for (int u = 1; u <= n; ++u) for (int v = 1; v <= n; ++v) if (u != v && !ee[u][v]) edge[u][et[u]++] = v; return n || m; } bool fill_color(int u) { int new_color = (color_n << 1) + 1 - color[u]; for (int i = 0, v = edge[u][0]; i < et[u]; v = edge[u][++i]) if (bcc[v] == bcc_n) { if (color[v] < color_n) { color[v] = new_color; if (fill_color(v)) return true; } else if (color[v] != new_color) { return true; } } return false; } int calc_bcc(int s, int t) { int last0 = stack_last++; ++bcc_n; do { --stack_last; bcc[stack[stack_last][0]] = bcc[stack[stack_last][1]] = bcc_n; } while (stack_last > 1 && (stack[stack_last][0] != s || stack[stack_last][1] != t)); color[s] = (color_n += 2); if (fill_color(s)) { for (int i = stack_last; i <= last0; ++i) point[stack[i][0]] = point[stack[i][1]] = 1; } --stack_last; return 0; } int dfs(int u, int father, int d) { int tot = 0; vis[u] = 1; deep[u] = low[u] = d; for (int i = 0, v = edge[u][0]; i < et[u]; v = edge[u][++i]) { if (!vis[v]) { stack[++stack_last][0] = u; stack[stack_last][1] = v; dfs(v, u, d + 1); ++tot; low[u] = low[u] < low[v] ? low[u] : low[v]; if (u == 1 || deep[u] <= low[v]) calc_bcc(u, v); } else if (v != father) { low[u] = low[u] < deep[v] ? low[u] : deep[v]; } } return 0; } int work() { memset(vis, 0, sizeof(vis)); memset(bcc, 0, sizeof(bcc)); memset(color, 0, sizeof(color)); memset(point, 0, sizeof(point)); bcc_n = color_n = stack_last = 0; for (int v = 1; v <= n; ++v) if (!vis[v]) dfs(v, 0, 1); int res = 0; for (int v = 1; v <= n; ++v) res += !point[v] ? 1 : 0; return res; } int main() { while (input()) printf("%d\n", work()); return 0; } |