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

[seanwu (winesap)]

※ 引述《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
推 DJWS: https://cs.stackexchange.com/questions/81290/
→ DJWS: https://reurl.cc/VLp6pZ
→ DJWS: 看了一下 Uri Zwick 2023的文章，除了O(VE)和矩陣乘法，沒有
→ DJWS: 更快的方法。
→ saladim: 這個是通過官方資測的程式之一 XDDD 不過現在知道有問題
→ saladim: 了就好
→ saladim: 感謝解惑~~~(更快的解法要請其他高手ORZ)
→ seanwu: leetcode的測資很多都很弱，不是邊界case測不出來，就是複
→ seanwu: 雜度不合理也能隨便加一些cut凹過
→ seanwu: 當然實際應用上是比較沒什麼關係，平常也沒人會考慮hash_m
→ seanwu: ap撞成O(n)的問題 XD
→ seanwu: (指複雜度的部份)