求解释

kirlay · 发表于 2014-9-24 21:45:28

书本P231
LOW[6]到底是1还是3？按照图上面的文字解释应该是1
书本P232，第一段
low[5]==num[3]我觉得按照你的解释应该是low[5]==num[2]，因为2才是5的father，而3是祖先

rosynirvana · 发表于 2014-9-24 23:07:53

lz要是方便的话给张书的图片？

超神级 · 发表于 2014-9-25 22:16:24

说i下我的理解！我想你可能理解错了！
数组num存的是每个定点的时间戳
而数组low存的是每个顶点不经过父(但是包含父）最小时间戳
也是是说
low[5]==num[3]这个段代码可以使用汉字描述为
顶点为5的时间戳在不经过父的情况下可以回到最小时间戳为3（即2号顶点）
广告下:..http://www.ahalei.com/thread-5686-1-1.html啊哈算法解答贴
//算法我也是草草的看了一遍也不是很熟悉根据大概描述一遍。如有错误请指出，

rosynirvana · 发表于 2014-9-25 22:31:58

超神级发表于 2014-9-25 22:16
说i下我的理解！我想你可能理解错了！
数组num存的是每个定点的时间戳
而数组low存的是每个顶点不经过父( ...

手头没书，求张照片

超神级 · 发表于 2014-9-25 23:42:16

rosynirvana 发表于 2014-9-25 22:31
手头没书，求张照片

恩恩！好的！私聊给你了！

rosynirvana · 发表于 2014-9-25 23:55:18

超神级发表于 2014-9-25 23:42
恩恩！好的！私聊给你了！

论坛pm？没收到……

超神级 · 发表于 2014-9-25 23:58:29

rosynirvana 发表于 2014-9-25 23:55
论坛pm？没收到……

一日一练看到了吗！你的帖子里

rosynirvana · 发表于 2014-9-25 23:59:35

超神级发表于 2014-9-25 23:58
一日一练看到了吗！你的帖子里

看到了，谢了，我研究研究看看

超神级 · 发表于 2014-9-26 00:10:30

rosynirvana 发表于 2014-9-25 23:59
看到了，谢了，我研究研究看看

.....

！

rosynirvana · 发表于 2014-9-26 00:38:03

超神级发表于 2014-9-25 22:16
说i下我的理解！我想你可能理解错了！
数组num存的是每个定点的时间戳
而数组low存的是每个顶点不经过父( ...

图片和文字是矛盾的吧，图上是low[6] == 3，文字描述是low[6] == 1

rosynirvana · 发表于 2014-9-26 01:55:20

仔细看了下楼主说的两点都是正确的，low[6]是1，因为有一条back edge可以回到根顶点
然后后面一个是num[2]

另外还有个问题，讨论low[1]是没有意义的，low成员的含义是不跨过父节点能到达的最早发现节点，1是整个DFS tree的根，没有父节点，讨论这个问题没有意义

根节点可以直接用DFS tree上面的根下面一级的子节点数目来判定(2-> 根节点是关键点，否则就不是）

超神级 · 发表于 2014-9-26 18:05:53

rosynirvana 发表于 2014-9-26 00:38
图片和文字是矛盾的吧，图上是low[6] == 3，文字描述是low[6] == 1

恩！是矛盾的！我记错了！

求解释

浏览过的版块