Re: [理工] 96 97 師大資工 DS&ALGO
97 7. 我怎麼畫都畫不出來，感覺DFS要"012345"才有可能，不然就是切點給錯了
請各位大大幫個忙 謝謝~
首先如果按照題目 a b c d e 全部不管
把原來矩陣上表示有的邊先連起來
圖形大概長像這樣
0----1----2----3
|
|
4----5
因為DFS順序是013245 表示1和3必相連 所以知道<a>=1
然後因為圖是無向的
所以矩陣對稱 得到 <f>=0 , <d>=1 ,<b>=<a>=1, <e>=<c>
最後剩下找<c>和<e> 但找完C就等於找e
再靠1,2,4為articulation point知道
<c>一定是0 點3 點4 必不相連
否則的話 點2就不是articulation point
所以<c>=<e>=0
a.b.c.d.e.f全找到了
依照以上敘述再看一下圖變成
---------
| |
0----1----2----3
|
|
4----5
驗證一下DFS順序013245 也合理
此題結束
---------#
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.82
※ 編輯: cksh3300110 來自: 140.112.30.82 (02/29 16:18)
※ 編輯: cksh3300110 來自: 140.112.30.82 (02/29 16:19)
推
02/29 16:21, , 1F
02/29 16:21, 1F