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