Re: [問題] LeetCode 2608. Shortest Cycle in a Graph

看板Prob_Solve (計算數學 Problem Solving)作者 (winesap)時間1年前 (2023/05/21 14:45), 編輯推噓1(1011)
留言12則, 3人參與, 1年前最新討論串2/2 (看更多)
※ 引述《saladim (殺拉頂)》之銘言: 部份引言恕刪 : 看不懂第36行寫這樣的理論基礎是什麼? 為什麼這時候就知道要再減一? : 而且他檢查的是第一根input edge的node, 跟traverse的順序也不一樣..... : 做了個實驗 如果我只是把case裡面的編號4跟5對調 跟原圖是一模一樣 traverse順序 : 也一樣 不過這段code會wrong answer........ : 想不到線索 請各位幫忙解惑一下 謝謝~~~ 因為他用的演算法根本是錯的啊XD 36行這樣寫只是硬把某些會錯的 testcase 修掉而已, 條件裡會出現 vertex index 根本毫無道理可言 (edge[0][0] == n-2) 好像圖的性質會跟你怎麼叫一個點有關一樣 ... 所以你對調測資裡的編號後它才會 WA 順便借問,這個問題我只能想到 O(|V||E|), 以題目來說應該是夠,但有更快的做法嗎? === 以下是這段code是錯誤的原因: 它要做的演算法是檢查所有 DFS traverse tree 上的 back edge (u,v) 因為 tree 上 path v->u 和 edge (u,v) 會形成一個 cycle, 它計算了 v->u 的路徑長度 (=深度差) 加上 (u,v) 的長度 (=1),然後更新最小值 mini // 上述的邏輯在 13-14 行 這個做法的假設是任意 cycle 一定會被 DFS 走到剩一條邊,但這是錯的 考慮下圖的反例: 13── 12── 11── 10── 9 ── 8 ╱ │ │ ╱ │ │ 0 │ │ 7 │ │ │ │ 1 ── 2 ── 3 ── 4 ── 5 ── 6 從 0 開始 DFS,不失一般性假設點編號序剛好是 DFS 順序, 則黃色邊是 DFS tree,而深度 vis[i] 會剛好等於 i 這裡只有三條 back edge: (10,4), (11,3), (13,0) 但三條邊對應的 cycle 是: 10-4-5-...-9-10: length = 10-4+1 = 7 11-3-4-...-10-11: length = 11-3+1 = 9 13-0-1-...-12-13: length = 13-0+1 = 14 而最小的 cycle 是 3-4-10-11-3,minimum length = 4 // 另外原code裡還有一個演算法實作上的錯誤, // 它把vis[i]同時當做深度和visited表來用,但第10行用 !vis[i] 來判斷, // 使得 vis[i]==0 的點 (起點) 會被多踩一次 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.229.71.95 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1684651548.A.D09.html

05/21 18:00, 1年前 , 1F

05/21 18:05, 1年前 , 2F

05/21 18:08, 1年前 , 3F
看了一下 Uri Zwick 2023的文章,除了O(VE)和矩陣乘法,沒有
05/21 18:08, 3F

05/21 18:08, 1年前 , 4F
更快的方法。
05/21 18:08, 4F

05/22 00:17, 1年前 , 5F
這個是通過官方資測的程式之一 XDDD 不過現在知道有問題
05/22 00:17, 5F

05/22 00:20, 1年前 , 6F
了就好
05/22 00:20, 6F

05/22 00:22, 1年前 , 7F
感謝解惑~~~(更快的解法要請其他高手ORZ)
05/22 00:22, 7F

05/22 08:15, 1年前 , 8F
leetcode的測資很多都很弱,不是邊界case測不出來,就是複
05/22 08:15, 8F

05/22 08:15, 1年前 , 9F
雜度不合理也能隨便加一些cut凹過
05/22 08:15, 9F

05/22 08:19, 1年前 , 10F
當然實際應用上是比較沒什麼關係,平常也沒人會考慮hash_m
05/22 08:19, 10F

05/22 08:19, 1年前 , 11F
ap撞成O(n)的問題 XD
05/22 08:19, 11F

05/22 08:20, 1年前 , 12F
(指複雜度的部份)
05/22 08:20, 12F
文章代碼(AID): #1aQRuSq9 (Prob_Solve)
文章代碼(AID): #1aQRuSq9 (Prob_Solve)