I have the following task about finding a cycle in a directed graph. https://www.eolymp.com/en/problems/2270

Here is my code, it passes 82%. Where can there be inaccuracies here? I did exactly according to the instructions for describing the algorithms.

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

Input: The first line contains two positive integers n and m (1 ≤ n ≤ 105, 1 ≤ m ≤ 105) - the number of vertices and edges in graph respectively. In the next m lines the edges are given. Each edge is described with a pair of numbers - the numbers of initial and final vertex respectively.

Output: If the graph does not contain the cycle, print "NO", otherwise print "YES" and then the list of vertices in the order of cycle traversal.

Example 1:

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

OUT:
YES
2 4 6 5

Example 2:

IN:
3 3
1 2
2 3
1 3

OUT:
NO

CodePudding user response：

The problem is that your code will print "NO" before having iterated all the nodes of the graph. This should not happen within the loop, but after. This is important in cases where the first DFS traversal does not reach all nodes, and there is a cycle in the nodes that it did not reach yet. So the cycle will only be detected in a future iteration of the loop.

Here is the correction of that driver code:

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

The else block now belongs to the for statement and will only execute when all iterations of the loop were executed without hitting a break.