Negative cycle detection P37940


Statement
 

pdf   zip

thehtml

Write a program that, given a directed graph with positive and/or negative costs at the arcs, detects if there is a negative cycle in the graph.

Input

Input consists of several cases. Every case begins with the number of vertices n and the number of arcs m. Follow m triples u, v, c, indicating that there is an arc u → v of cost c, where u ≠ v, −106 ≤ c ≤ 106. Assume 1 ≤ n ≤ 104, 0 ≤ m ≤ 5n, and that for every pair of vertices u and v there is at most one arc of the kind u → v. All numbers are integers. Vertices are numbered from 0 to n−1.

Output

For every case, print "YES" if there is a negative cycle in the graph, and "NO" otherwise.

Public test cases

  • Input

    4 4
    0 3 6
    1 0 4
    3 1 -11
    1 2 -6

4 4
    0 3 6
    1 0 4
    3 1 2
    1 2 -6

2 2
    0 1 10
    1 0 10

2 2
    0 1 10
    1 0 -20

2 2
    0 1 10
    1 0 -10

    Output

    YES
NO
NO
YES
NO
    • Information
    Author
    Jordi Petit
    Language
    English
    Official solutions
    Python
    User solutions
    Python