割点与桥

TAG 图论 割点 桥

原帖地址：http://www.cppblog.com/Icyflame/archive/2009/07/05/89227.html

/*

我的理解：刚开始思考怎么算割点，我的思路是如果去掉该点，再从该节点的任意一个邻接节点出发，如果不能遍历其他全部节点，那该点就是割点。显然很蛋疼，每个点都要去dfs一次。这里面有很多冗余运算。

举一个例子，一条链，0-1-2-3-...-n 这样，从0开始，每次遍历都是相似的，后面的被遍历很多遍。

我就想，能不能在第一次遍历的时候记录下相应的信息，供后面调用。我感觉可以标一下号。

如果割点去掉，可以看作图被分成左右两个分支（简化分析,当然还能分成3个分支哦），我们知道从右边的点开始访问不能“窜到“左边的点。我感觉可以记录该节点的某个能力值，通过这个值来判断是否能访问到左边。

当然，大体的思路是有了，但我可没能想出具体的算法，不过有了前面的思考，理解下面的算法就比较简单了

*/

一、定义
割点：如果在图G中删去一个结点u后，图G的连通分枝数增加，即W(G-u)>W(G)，则称结点u为G的割点，又称关节点。
桥：如果在图G中删去一条边e后，图G的连通分支数增加，即W(G-e)>W(G)，则称边u为G的桥，又称割边或关节边。
双连通分支：G中不含割点的极大连通子图称为G的双连通分支，又称为G的块。

/* 有桥一定有割点，有割点不一定有桥。hit：该割点的边很多。。*/

二、DFS
描述： 在对于任选一个图中结点为根的DFS搜索树中建立一个LAB数组与LOW数组，LAB数组存储个结点的编号，LOW数组存储各点及其子树的各结点能到达的最小编号结点的编号。

1 //lab为一个全局变量，初始为1， LAB各项初始为0
2 DFS(u)
3     LAB[u] = LOW[u] = lab++
4     for each (u, v) in E(G)
5         if LAB[v] is 0
6             DFS(v)
7             LOW[u] = min{LOW[u], LOW[v]}
8         else if  v isnot parent of u
9             LOW[u] = min{LOW[u], LAB[v]}

第5行中，如果(u, v)是树边，则对v做深度优先搜索，并且LOW[u] = min{LOW[u], LOW[v]}，如果(u, v)是反向边，则LOW[u] = min{LOW[u], LAB[v]}。
三、割点
描述： 当一个结点u是割点时必满足以下两个条件之一：
1）u为根且至少有两棵子树；
2）u不为根且存在一个u在深搜树中的子女v使得LOW[v]≥ LAB[u]。
示例： POJ 1523 解题报告 。
四、桥
描述： 一条边e=(u, v)是桥，当且仅当e为树枝边且LOW[v] > LAB[u]。
示例： POJ 3352 解题报告 。