[問題] LeetCode 2608. Shortest Cycle in a Graph
看板Prob_Solve (計算數學 Problem Solving)作者saladim (殺拉頂)時間1年前 (2023/05/21 03:13)推噓0(0推 0噓 0→)留言0則, 0人參與討論串1/2 (看更多)
https://leetcode.com/problems/shortest-cycle-in-a-graph/
最近在解這題 我自己是用DFS+BFS解掉 但是performance不是很好
所以看了一下最快的某個解法 但是其中有一行看不懂為什麼是這樣寫
附上他的code跟其中一個case(因為最快解法的出現次序會變動):
https://pastebin.com/sQWG6L8q
case:
n = 6,
edges = [[4,1],[3,2],[5,0],[3,0],[4,0],[2,1],[5,1]]
看不懂第36行寫這樣的理論基礎是什麼? 為什麼這時候就知道要再減一?
而且他檢查的是第一根input edge的node, 跟traverse的順序也不一樣.....
做了個實驗 如果我只是把case裡面的編號4跟5對調 跟原圖是一模一樣 traverse順序
也一樣 不過這段code會wrong answer........
想不到線索 請各位幫忙解惑一下 謝謝~~~
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.164.102.233 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1684610032.A.563.html
※ 編輯: saladim (1.164.102.233 臺灣), 05/21/2023 03:37:14
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章