割点和桥
/* *定义 * 割点：如果在图G中删去一个结点u后,图G的连通分枝数增加,即W(G-u)>W(G),则称结点u为G的割点,又称关节点; * 桥：如果在图G中删去一条边e后,图G的连通分支数增加,即W(G-e)>W(G),则称边u为G的桥,又称割边或关节边; * 双连通分支：G中不含割点的极大连通子图称为G的双连通分支,又称为G的块; * * *DFS * 描述： * 在对于任选一个图中结点为根的DFS搜索树中建立一个LAB数组与LOW数组; * LAB数组存储个结点的编号,LOW数组存储各点及其子树的各结点能到达的最小编号结点的编号; * * DFS(u) //lab为一个全局变量,初始为1,LAB数组各项初始为0; * LAB[u] = LOW[u] = lab++ //1 * for each (u, v) in E(G) //2 * if LAB[v] is 0 //3 * DFS(v) //4 * LOW[u] = min{LOW[u], LOW[v]} //5 * else if v isnot parent of u //6 * LOW[u] = min{LOW[u], LAB[v]} //7 * 第3行中,如果(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]; * * *桥 * 描述： * 一条边e=(u,v)是桥,当且仅当e为树枝边且LOW[v]>LAB[u]; ***/