作者ccmvic (Vic)
看板Grad-ProbAsk
標題106成大資結(7) （9）求詳解
時間Fri Feb 22 08:14:36 2019
各位好
求這兩題詳解
https://i.imgur.com/q5i9QGL.jpg
https://i.imgur.com/ABfPaJL.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.12.162.145
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1550794479.A.2EB.html
※ 編輯: ccmvic (39.12.162.145), 02/22/2019 08:17:30
1F：推 WachinMs: 7.用 dfs 找是否存在 back edge 02/22 08:45
2F：→ WachinMs: 8. 先求 SCC 建構出component graph H ,對 H 做拓樸排 02/22 08:45
3F：→ WachinMs: 序並驗證他是否存在 linear chain 02/22 08:45
4F：推 oldelette: 可以請教一下 為什麼有拓撲 就會等價有semi connected 02/22 08:56
5F：→ oldelette: 嗎？ 02/22 08:56
6F：推 eric131204: 因為只要兩點有一點可以走到另一點就好，所以不用強連 02/22 08:59
7F：→ eric131204: 通，用SCC圖作拓樸只要有一條路同方向連起來就可以保 02/22 08:59
8F：→ eric131204: 證所有在某個SCC的點可以走到另一個SCC的點。 02/22 08:59
9F：→ oldelette: 所以semi 定義是兩點之間有單向path就算嗎 有估狗過但 02/22 09:07
10F：→ oldelette: 找不太到 好像不是完全等於弱連通？ 02/22 09:07
11F：推 eric131204: 弱連通不是在講undirected嗎？我不太確定 02/22 09:12
12F：→ oldelette: Directed 才有分強弱吧 因為有方向問題 先謝謝e大！ 02/22 09:20
13F：推 eric131204: 弱連通是把digraph視為undirected如果是連通就算嗎 02/22 09:25
14F：推 oldelette: 應該是 02/22 09:41
15F：推 eric131204: 那就跟semi不一樣吧，像rooted tree把edge畫父到子的 02/22 09:46
16F：→ eric131204: 方向，那子點就互相走不到，但他也算弱連通吧？ 02/22 09:46
17F：→ ekids1234: 第7題要寫 "不能" 對吧 ? 只在O(V)有點吃圖 要O(V+E)? 02/22 10:15
18F：→ CorkiN: 那題題目意思是要你寫一個演算法決定圖中是否有含cycle @@ 02/22 10:18
19F：推 eric131204: O(V)就可以了吧，只是找有沒有cycle最多就檢查V-1個ed 02/22 10:30
20F：→ eric131204: ge，再超過就必有cycle了 02/22 10:30
21F：推 Rioronja: 同意樓上 雖然dfs是O(V+E) 但實際運作頂多O(V) 02/22 11:00
22F：推 rustw2010: 是要寫algo版的嗎 02/22 21:53
23F：推 nn410375yi: 先知 第一題猛 02/23 12:10
24F：推 eric131204: 朝聖一下 完全考一樣 02/23 13:00
25F：推 alen0303: 考題命中 恭喜 02/23 16:50
26F：噓 magic83v: QQ不會寫 02/24 07:28