Cycle Finding

题目描述

给定一个有向图，你的任务是判断它是否包含负环，并给出一个这样的环的例子。

输入格式

第一行包含两个整数 n 和 m：节点数和边数。节点编号为 1,2,$\ldots$,n。 接下来有 m 行描述边。每行有三个整数 a、b 和 c：存在一条从节点 a 到节点 b 的边，长度为 c。

输出格式

如果图包含负环，首先输出 “YES”，然后按正确的顺序输出环中的节点。如果存在多个负环，可以输出其中任意一个。如果不存在负环，输出 “NO”。

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

YES
1 2 4 1

提示

$1 \le n \le 2500$ $1 \le m \le 5000$ $1 \le a,b \le n$ $-10^9 \le c \le 10^9$

标签: CSES1197|图论

来源

CSES1197|图论