推 WachinMs: 7.用 dfs 找是否存在 back edge 02/22 08:45
→ WachinMs: 8. 先求 SCC 建構出component graph H ,對 H 做拓樸排 02/22 08:45
→ WachinMs: 序並驗證他是否存在 linear chain 02/22 08:45
推 oldelette: 可以請教一下 為什麼有拓撲 就會等價有semi connected 02/22 08:56
→ oldelette: 嗎？ 02/22 08:56
推 eric131204: 因為只要兩點有一點可以走到另一點就好，所以不用強連 02/22 08:59
→ eric131204: 通，用SCC圖作拓樸只要有一條路同方向連起來就可以保 02/22 08:59
→ eric131204: 證所有在某個SCC的點可以走到另一個SCC的點。 02/22 08:59
→ oldelette: 所以semi 定義是兩點之間有單向path就算嗎 有估狗過但 02/22 09:07
→ oldelette: 找不太到 好像不是完全等於弱連通？ 02/22 09:07
推 eric131204: 弱連通不是在講undirected嗎？我不太確定 02/22 09:12
→ oldelette: Directed 才有分強弱吧 因為有方向問題 先謝謝e大！ 02/22 09:20
推 eric131204: 弱連通是把digraph視為undirected如果是連通就算嗎 02/22 09:25
推 oldelette: 應該是 02/22 09:41
推 eric131204: 那就跟semi不一樣吧，像rooted tree把edge畫父到子的 02/22 09:46
→ eric131204: 方向，那子點就互相走不到，但他也算弱連通吧？ 02/22 09:46
→ ekids1234: 第7題要寫 "不能" 對吧 ? 只在O(V)有點吃圖 要O(V+E)? 02/22 10:15
→ CorkiN: 那題題目意思是要你寫一個演算法決定圖中是否有含cycle @@ 02/22 10:18
推 eric131204: O(V)就可以了吧，只是找有沒有cycle最多就檢查V-1個ed 02/22 10:30
→ eric131204: ge，再超過就必有cycle了 02/22 10:30
推 Rioronja: 同意樓上 雖然dfs是O(V+E) 但實際運作頂多O(V) 02/22 11:00
推 rustw2010: 是要寫algo版的嗎 02/22 21:53
推 nn410375yi: 先知 第一題猛 02/23 12:10
推 eric131204: 朝聖一下 完全考一樣 02/23 13:00
推 alen0303: 考題命中 恭喜 02/23 16:50
噓 magic83v: QQ不會寫 02/24 07:28