106成大資結(7) （9）求詳解

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