[理工] 关节点 99北大资工

楼主: PR58 (PowerRanger)   2015-01-27 10:29:54
题目:http://ppt.cc/XZ0W
我手边的答案是
node 1 2 3 4 5 6 7 8 9
dfn 4 3 2 5 1 6 9 7 8
low 4 1 1 1 1 6 6 6 8
所以是articulation point为 2 4 6 8
我自己写的是
node 1 2 3 4 5 6 7 8 9
dfn 4 3 2 5 1 6 9 7 8
low 4 3 2 3 1 6 6 6 8
我不知道我错在哪边,希望有人可以指点一下..
然后还想问biconnected component怎么判断?
因为我都用"感觉"的,是要根据什么讯息来判断吗?
谢谢
作者: jason82714 (Jason)   2015-01-27 11:32:00
我画出来的DFS TREE http://ppt.cc/Fb3r之后推出来的数字和你给的答案一样 我猜可能是你画错对了 红笔代表是Back Edge
作者: shanbb (Moriz)   2015-01-27 11:41:00
是不是没考虑到儿子或后代子孙有连Back edge的也会连过去
楼主: PR58 (PowerRanger)   2015-01-27 13:08:00
我耍笨了 真的画错 我知道哪边错了 感谢两位

Links booklink

Contact Us: admin [ a t ] ucptt.com