是不是没法通过BFS推算回cycle_path了

Question

好像没法通过pre来倒推回环路了
【测试用例】
顶点数: 7, 边数: 6
0: 1 2
1: 0 3 4
2: 0 3 6
3: 1 2
4: 1
5:
6: 2

【遍历顺序】
v: 0 出列
–w: 1 未访问，入列
–w: 2 未访问，入列
v: 1 出列
–w: 0 已访问，v: 1，v[pre]: 0，不符合要求
–w: 3 未访问，入列
–w: 4 未访问，入列
v: 2 出列
–w: 0 已访问，v: 2，v[pre]: 0，不符合要求
–w: 3 已访问，v: 2，v[pre]: 0，!= w，符合要求
----w: 3 已找到环

此时：pre = [0, 0, 0, 1, 1, -1, -1]
通过pre[3]倒推，然后死循环了

Answer 1

liuyubobobo 2020-02-18 12:10:34

是的，如果要寻找环具体是怎样的，不能使用 BFS：）

继续加油！：）

• 提问者 慕粉2011219583 #1

  非常感谢！否则要陷进去出不来了