Нислэгийн чиглэл шалгах

2s

512MB

1397

0%

Graph Algorithms

$n$ хот, $m$ нислэгийн холболт бий. Байгаа нислэгүүдийг ашиглан аливаа хотоос өөр аливаа хот руу зорчих боломжтой эсэхийг шалга.

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

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

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

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

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

Бүх чиглэл боломжтой бол "YES", үгүй бол "NO" гэж хэвлэ. Хоёр дахь тохиолдолд $a$ хотоос $b$ хот руу зорчих боломжгүй $a$ , $b$ хоёр хотыг мөн хэвлэ. Хэд хэдэн шийдэл байвал аль нэгийг нь хэвлэж болно.

Хязгаарлалт

$1 \le n \le 10^5$
$1 \le m \le 2 \cdot 10^5$
$1 \le a,b \le n$

Жишээ

Оролт1

Гаралт1

NO
4 2

0.1 / 64 KiB

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