tarjan算法中比较dfn 还是low

网友投稿 1011 2022-08-29

tarjan算法中比较dfn 还是low

tarjan算法中比较dfn 还是low

假设按以下顺序dfs,括号里表示的是回溯的过程

0-1-2-3-0(-3-2)-4-5-2(-5-4-2)-5(-2-1-0)-3(-0)

low和dfn比较:low[0]=low[1]=low[2]=low[3]=0

low[4]=low[5]=2

low和low比较:全部都是0…

问题出在low[5]上,如果是low[5]和dfn[2]比较low[5]=2,如果是和low[2]比较,low[5]=0

当low[5]=2的时候,2判断是割点,当low[5]=0的时候,2判断就不是割点了。

而实际上2是割点。 但是如果求强连通的时候大概影响无法体现 所以错误写法也是对的 但建议还是直接写dfn比较好

版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:php的命名空间和自动加载实现(php类的自动加载方式)
下一篇:luogu1099 树网的核
相关文章

 发表评论

暂时没有评论,来抢沙发吧~