为什么我的代码在DG中找到一个循环不能正确工作?

Question

我有以下关于在有向图中找到一个循环的任务。https://www.eolymp.com/en/problems/2270

这是我的代码，它通过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

Answer 1

问题是你的代码将打印"NO"在迭代图的所有节点之前。这不应该在循环内发生，而应该在循环之后发生。在第一次DFS遍历没有到达所有节点，并且在它尚未到达的节点中存在一个循环的情况下，这一点很重要。因此，只有在循环的未来迭代中才会检测到循环。

下面是该驱动程序代码的更正:

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')

else块现在属于for语句，并且只有在循环的所有迭代都执行而没有遇到break时才会执行。