[理工] 關節點 99北大資工
作者: PR58 (PowerRanger) 2015-01-27 10:29:54
題目：
![]()
我手邊的答案是
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怎麼判斷?
因為我都用"感覺"的，是要根據什麼訊息來判斷嗎?
謝謝
我手邊的答案是
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 ![]()
" target="_blank" rel="nofollow">
![]()
之後推出來的數字和你給的答案一樣 我猜可能是你畫錯對了 紅筆代表是Back Edge
" target="_blank" rel="nofollow">之後推出來的數字和你給的答案一樣 我猜可能是你畫錯對了 紅筆代表是Back Edge作者: shanbb (Moriz) 2015-01-27 11:41:00
是不是沒考慮到兒子或後代子孫有連Back edge的也會連過去
作者: PR58 (PowerRanger) 2015-01-27 13:08:00
我耍笨了 真的畫錯 我知道哪邊錯了 感謝兩位