有向图(DG)环检测代码仅通过82%用例，求错误原因

我正在完成有向图中检测环的任务，代码仅通过了82%的测试用例，但我是严格按照算法说明实现的，请问可能存在哪些问题？

我的代码 #

def dfs(start_v, G, Color, path, result):
    Color[start_v] = 1
    for i in G[start_v]:
        if Color[i] is None:
            path.append(i)
            dfs(i, G, Color, path, result)
            path.pop()
            if len(result) > 0:
                return
        elif Color[i] == 1:
            result.extend(path[path.index(i):])
            return
    Color[start_v] = 2


N, M = map(int, input().split())
Graph = [set() for i in range(N + 1)]
Color = [None] * (N + 1)
result = []

for i in range(M):
    a, b = map(int, input().split())
    Graph[a].add(b)
i = 1
for i in range(N, 0, -1):
    if Color[i] is None:
        dfs(i, Graph, Color, [i], result)
        if len(result) > 0:
            print("YES")
            print(" ".join(map(str, result)))
            break
        else:
            print('NO')
            break

题目要求 #

输入要求 #

第一行包含两个正整数n和m（1 ≤ n ≤ 105, 1 ≤ m ≤ 105），分别表示图的顶点数和边数。接下来m行每行给出一条边，包含两个数字，分别表示边的起点和终点。

输出要求 #

如果图中不存在环，输出"NO"；否则输出"YES"，并按遍历顺序输出环中的顶点列表。

示例 #

示例1 #

IN:
6 7
1 2
1 5
2 3
2 4
4 6
6 5
5 2

OUT:
YES
2 4 6 5

示例2 #

IN:
3 3
1 2
2 3
1 3

OUT:
NO

问题分析 #

你的代码存在几个关键问题，导致无法通过所有测试用例：

• 错误的终止逻辑：你在遍历第一个未访问的连通分量后，若没找到环就直接输出"NO"并终止程序。但图可能存在多个连通分量，后续分量中可能存在环，这会导致误判。比如第一个分量无环，但第二个分量有环时，你的代码会错误输出"NO"。

• path.index(i)的性能问题：list.index()是O(k)时间复杂度（k为当前路径长度），当处理1e5规模的图时，这会导致超时，无法通过大数据量的测试用例。

修改建议 #

1. 修正终止逻辑：遍历所有节点，只有当所有连通分量都检测完毕且未找到环时，才输出"NO"。

2. 优化节点位置查找：用一个数组记录每个节点在当前路径中的位置，将查找操作降为O(1)。

3. 可选优化：将邻接表从set改为list，set遍历顺序不确定，但题目不要求环的具体顺序，所以不影响正确性，但list的遍历效率略高。

修改后的代码示例 #

def dfs(start_v, G, color, path, pos, result):
    color[start_v] = 1
    pos[start_v] = len(path)
    path.append(start_v)
    for neighbor in G[start_v]:
        if color[neighbor] is None:
            dfs(neighbor, G, color, path, pos, result)
            if result:
                return
        elif color[neighbor] == 1:
            # 提取环：从neighbor在path中的位置到当前节点
            result.extend(path[pos[neighbor]:])
            return
    color[start_v] = 2
    pos[start_v] = -1  # 标记不在路径中
    path.pop()


n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]
color = [None] * (n + 1)
pos = [-1] * (n + 1)  # 记录节点在path中的索引，-1表示不在路径
result = []

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)

for i in range(1, n + 1):
    if color[i] is None and not result:
        dfs(i, graph, color, [], pos, result)

if result:
    print("YES")
    print(" ".join(map(str, result)))
else:
    print("NO")

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