PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

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

看板Prob_Solve (計算數學 Problem Solving)作者seanwu (winesap)時間1年前 (2023/05/21 14:45)推噓1(1推 0噓 11→)

留言12則, 3人參與討論串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