Цикл олох

2s

512MB

1294

0%

Graph Algorithms

Чиглэлтэй граф өгөгдсөн; сөрөг цикл байгаа эсэхийг тодорхойл, байгаа бол ийм циклийн жишээг өг.

https://cses.fi/problemset/task/1197

Оролтын формат

Эхний мөрөнд $n$ ба $m$ хоёр бүхэл тоо байна: орой болон ирмэгийн тоо. Оройгууд $1,2,\ldots,n$ гэж дугаарлагдсан.

Дараа нь ирмэгүүдийг тодорхойлсон $m$ мөр байна. Мөр бүрт $a$ , $b$ , $c$ гурван бүхэл тоо байна: $a$ оройгоос $b$ орой руу урт нь $c$ ирмэг бий.

Гаралтын формат

Графт сөрөг цикл байвал эхлээд "YES", дараа нь цикл дэх оройгуудыг зөв дарааллаар хэвлэ. Сөрөг цикл олон байвал алийг нь ч хэвлэж болно. Сөрөг цикл байхгүй бол "NO" хэвлэ.

Хязгаарлалт

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

Жишээ

Оролт1

Гаралт1

YES
1 2 4 1

0.1 / 64 KiB

Редактор уншиж байна...