算法合集之图论基本思想及的方法.ppt

可知点v 一定是边(u, v)所在域的极低点 根据DFS中点的状态和指针pre就可以按如下方法确定图G中的域 当检查点u的某条边时发现边的另一个顶点v已经被扩展完毕 而pre[v]和u最近公共祖先点一定是域的极高点 v pre[v] u vh 极高点 极低点 算法设计DFS 寻找pre[v]和u的最近公共祖先只需要利用pre回溯寻找v的祖先第一个未被扩展完毕的祖先便是域的极高点 从v到pre[v