※ 引述《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 的點 (起點) 會被多踩一次