[理工] 清大104計科第8題

[visual (米干)]

題目：http://imgur.com/a/9NvE4


我寫出來的dfn值為


vertex  0  1  2  3  4  5  6  7  8  9

 dfn    8  7  9  6  10 3  4  2  1  5


然後畫出來的dfs圖：http://imgur.com/a/OHrn6


請問我有畫錯嗎?然後想再請問一下題目問low[1]，是指所有low = 1的vertex嗎?

謝謝大家~


祝大家明天考試順利~~

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.52.134.18
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1486550247.A.ABB.html
→ s89162504: 是指點1的low值
推 weilun911: http://i.imgur.com/27rMxBS.jpg
→ weilun911: 我是這樣畫給你參考
→ visual: 想問一下w大 那他題目裡面說的dfn[3]=5是...?
推 hut326521: 那是指用DFS 走訪的順序
→ hut326521: 印象中這題下面有dfnlow的程式碼 然後題目說要從-5開
→ hut326521: 始走
→ hut326521: 打錯 從5開始走
→ hut326521: 然後第五個走到3 第六個走到1
→ hut326521: 阿阿我少說了 順序從0開始
推 hut326521: 所以是第六個走到3 第七個走到4
→ hut326521: 走訪順序5678934210
→ PTTleader:    dfn是0123456789喔
→ PTTleader: 配合hut大的XD
→ PTTleader:    low是0003455559      應該沒錯拉
推 machia045413: 想問一下 一開始num不是0嗎 且有一行有num++ 不懂
→ machia045413: 為何5的dfn low都是0
推 yupog2003: dfn[u]=low[u]=num++是先assign再++喔
→ yupog2003: 如果是dfn[u]=low[u]=++num，就會是1
→ visual: 啊!我懂了 謝謝hut大~
→ visual: 我搞錯題目的意思了XD
推 z83420123: 所以起始點是w大搞錯對不對？
推 weilun911: 摁 我5和6的DFN寫相反了