Tarjan算法求图中割边(Cut Edge)代码故障排查及验证咨询

你的Tarjan割边实现有两个核心错误，是大测试用例失败的主要原因：

• 割边判定条件错误：
  原代码的判定逻辑if(low[v] > low[u])不符合Tarjan算法规则，正确的判定应该是if(low[v] > disc[u])。只有当子节点v的low值大于父节点u的发现时间disc[u]时，才说明v无法通过任何回边到达u或更早被发现的节点，此时u-v才是割边。你用low[u]做比较的逻辑会因为low[u]后续被回边更新变小，导致漏判或误判割边。
• 时间戳time是值传递，无法同步更新：
  Java中int是值类型，你将time作为参数递归传递时，子递归中对time的修改不会同步到上层递归，会导致多个节点的发现时间disc重复赋值，小测试用例中因为递归层级浅、邻接点少不容易触发，大测试用例必然会出现逻辑异常。你可以把time改成长度为1的int数组传递，通过修改数组元素值实现跨递归层的时间同步。

• 先修复上述两个错误后重新运行失败的测试用例，若运行通过则说明是代码问题，不需要怀疑测试用例合法性。
• 修复前可以先跑公开基础样例验证：比如输入n=4，连接为[[0,1],[1,2],[2,0],[1,3]]，预期输出是[[1,3]]，你用原代码运行会得到错误结果，即可确认代码问题。
• 如果修复后仍失败，可以将大图的边集导出，用其他已验证的割边工具跑一遍，对比结果差异即可定位是代码剩余问题还是测试用例问题。

内容的提问来源于stack exchange，提问作者Ankit Chauhan