106成大資結(7) （9）求詳解 ccmvic PTT批踢踢實業坊

作者: ccmvic (Vic) 2019-02-22 08:14:36

各位好
求這兩題詳解
https://i.imgur.com/q5i9QGL.jpg
https://i.imgur.com/ABfPaJL.jpg

作者: WachinMs (NK) 2019-02-22 08:45:00

7.用 dfs 找是否存在 back edge8. 先求 SCC 建構出component graph H ,對 H 做拓樸排序並驗證他是否存在 linear chain

作者: oldelette (oldelette) 2019-02-22 08:56:00

可以請教一下為什麼有拓撲就會等價有semi connected嗎？

作者: eric131204 (暗女巫) 2019-02-22 08:59:00

因為只要兩點有一點可以走到另一點就好，所以不用強連通，用SCC圖作拓樸只要有一條路同方向連起來就可以保證所有在某個SCC的點可以走到另一個SCC的點。

作者: oldelette (oldelette) 2019-02-22 09:07:00

所以semi 定義是兩點之間有單向path就算嗎有估狗過但找不太到好像不是完全等於弱連通？

作者: eric131204 (暗女巫) 2019-02-22 09:12:00

弱連通不是在講undirected嗎？我不太確定

作者: oldelette (oldelette) 2019-02-22 09:20:00

Directed 才有分強弱吧因為有方向問題先謝謝e大！

作者: eric131204 (暗女巫) 2019-02-22 09:25:00

弱連通是把digraph視為undirected如果是連通就算嗎

作者: oldelette (oldelette) 2019-02-22 09:41:00

應該是

作者: eric131204 (暗女巫) 2019-02-22 09:46:00

那就跟semi不一樣吧，像rooted tree把edge畫父到子的方向，那子點就互相走不到，但他也算弱連通吧？

作者: ekids1234 (∵:☆星痕╭☆) 2019-02-22 10:15:00

第7題要寫 "不能" 對吧 ? 只在O(V)有點吃圖要O(V+E)?

作者: CorkiN (柯基) 2019-02-22 10:18:00

那題題目意思是要你寫一個演算法決定圖中是否有含cycle @@

作者: eric131204 (暗女巫) 2019-02-22 10:30:00

O(V)就可以了吧，只是找有沒有cycle最多就檢查V-1個edge，再超過就必有cycle了

作者: Rioronja (想show幹話組) 2019-02-22 11:00:00

同意樓上雖然dfs是O(V+E) 但實際運作頂多O(V)

作者: rustw2010 (cherish) 2019-02-22 21:53:00

是要寫algo版的嗎

作者: nn410375yi (nnyi) 2019-02-23 12:10:00

先知第一題猛

作者: eric131204 (暗女巫) 2019-02-23 13:00:00

朝聖一下完全考一樣

作者: alen0303 (艾倫零參智商負三) 2019-02-23 16:50:00

考題命中恭喜

作者: magic83v (R7) 2019-02-24 07:28:00

QQ不會寫

繼續閱讀