#T2095. 环的检测(Cycle Finding)

环的检测(Cycle Finding)

链接: https://cses.fi/problemset/task/1196

板块: Graph Algorithms

时限: 1.00 s | 内存: 512 MB

题目描述

给定一个有向图,你的任务是判断其中是否包含负权环,并给出一个这样的环的示例。

输入

第一行输入包含两个整数 nn 和 mm:节点数和边数。节点编号为 1,2,…,n1,2,\ldots,n。

之后有 mm 行描述边。每行包含三个整数 aa、bb 和 cc:存在一条从节点 aa 到节点 bb 的边,长度为 cc。

输出

如果图包含负权环,先输出 "YES",然后按正确顺序输出环上的节点。如果有多个负权环,你可以输出任意一个。如果没有负权环,输出 "NO"。

数据范围

1≤n≤25001 \le n \le 2500 1≤m≤50001 \le m \le 5000 1≤a,b≤n1 \le a,b \le n −109≤c≤109-10^9 \le c \le 10^9

样例输入

4 5
1 2 1
2 4 1
3 1 1
4 1 -3
4 3 -2

样例输出

YES
1 2 4 1