※ 引述《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://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1684651548.A.D09.html