无向图双连通分量及其性质 pku2942

2. [PKU 2942]
   
3. 
   
4. 2009-07-16
   
5. 
   
6. N个骑士开圆桌会议, 有些骑士不能相邻, 要求每桌奇数个人, 每桌至少3个人, 问哪些骑士永
   
7. 远不能参加圆桌会议.
   
8. 
   
9. 将不能相邻的点连起来, 建补图, 则问题转化为那些点不在奇数个顶点的圈中.
   
10. 
    
11. 先求此无向图的点的双连通分量(Point Biconnected Component), 注意不是边的双连通分
    
12. 量(Edge Biconnected Component). 因为不在同一个点双连通分量中的两个点不可能在同
    
13. 一个奇数圈中. 注意点的双连通分量与边的双连通分量的求法是不同的).
    
14. 
    
15. [点的双连通分量的求法]
    
16. 
    
17. 首先求出割点: 给每个顶点定义一个low值, low(u)表示从u出发, 经过一条其后代组成的路径
    
18. 和后向边, 所能到达的最小深度的顶点的编号(如果这个编号大于等于u的编号, 就说明它的后代
    
19. 无法到达比u深度更浅的顶点, 即无法到达u的祖先, 那么u就是个关节点, 具体做法是在DFS每
    
20. 次回溯后拿刚才扩展节点的low与当前节点的dfn比较, 若low>=dfn则当前节点是割点).
    
21. 
    
22. low(u)=min{dfn(u), min{low(w)|w是u的儿子}, min{dfn(w)|(u,w) 是一条后向边}}
    
23. dfn(u)是深搜过程中对顶点的编号值.
    
24. 
    
25. 在求割点的同时就可以通过一个全局的栈求出点的双连通分量, 具体做法是在DFS每次由当前顶
    
26. 点u深入下一顶点v时, 就将边uv进栈, 若在函数返回后判断出v是割点, 则出栈, 直到uv出栈,
    
27. 刚才出栈的这些边就属于同一个点双连通分量.
    
28. 
    
29. 伪代码如下: (dfn[]初始为0)
    
30. void pbc_dfs(int u, int parent) {
    
31.     dfn[u] = low[u] = dfn_now++;
    
32.     foreach e in adjacent list [u] {
    
33.         v = e->v;
    
34.         if (v != parent && dfn[v] < dfn[u]) {
    
35.             stack.push(Edge(u, v));
    
36.             if (0 != dfn[v]) low[u] = min(low[u], dfn[v]);
    
37.             else {
    
38.                 pbc_dfs(v, u);
    
39.                 low[u] = min(low[u], low[v]);
    
40.                 if (dfn[u] >= low[v]) { // u is a cut point
    
41.                     do {
    
42.                         Edge edg = stack.pop();
    
43.                         ...(some operation)
    
44.                     } while(edg is not uv);
    
45.                     ++component_id;
    
46.                 }
    
47.             }
    
48.         }
    
49.     }
    
50. }
    
51. 
    
52. 注意在无向图深搜树中, 只有两种边: 树边(u->v u是v的父亲, v未访问)和后向边(u->v,
    
53. v是u的祖先, v访问过)。 且无向图的边在邻接表中其实是"双向"的。因此我们要通过一些条
    
54. 件来只使用树边和后向边.
    
55. 因此对于边uv, dfn[u]dfn[v](v
    
56. 是u的父亲(树边的反向)), 这两种都是已经访问过的边, 不需要重复访问.
    
57. 
    
58. end of [点的双连通分量的求法]
    
59. 
    
60. 求出所有点双连通分量后就是要求每个点双连通分量中的点是否在某个奇数顶点的圈中, 这里需
    
61. 要用到两条定理:
    
62. 1. 一个点双连通分量中如果存在一个奇数顶点的圈, 那么此分量的所有点都在某个奇数圈中.
    
63. 2. 一个点双连通分量有奇数圈, 与这个分量不是二分图等价.
    
64. 
    
65. 直观的证明:
    
66. 1. 若此分量有奇数个点, 那么由于此分量中一定有一条回路连接所有点, 所以得证; 若此分量
    
67. 中有偶数个点, 那么如果有一个奇数点的圈, 那么剩余点一定是奇数个, 剩余的点要么能依靠
    
68. 这个圈以外的边够成奇数顶点圈, 要么它需要依靠已有的奇数顶点圈上的边够成一个圈, 又在奇
    
69. 数顶点的圈上任取两点一定可以把圈分成奇数点和偶数点的两部分, 取偶数点的那部分与剩下的
    
70. 点结合就一定能构成另一个奇数顶点的圈.
    
71. 2. 反证法, 若此分量为二分图, 那么从一个点出发一定要经过偶数条边才能回来, 这是显然,
    
72. 的想像在河的一边出发总要过偶数次河才能回到原来的一边.
    
73. 
    
74. 这样只要判断每个分量是否是二分图即可, 用DFS或BFS对相邻点染黑白两色, 相邻点不同色,
    
75. 若遇到已染色且与当前点颜色相同则不是二分图(1).
    
76. 
    
77. 另外要特别注意割点可以在多个点连通分量中, 所以每次做算法(1)时必须将标记数组清空, 并
    
78. 且不能直接计算二分图顶点总数, 而是要计算非二分图顶点总数.
    
79. 
    
80. 连通图的定义等参见: http://www.byvoid.com/blog/biconnect/
    
81. */

复制代码