Шинэ Нислэгийн Чиглэлүүд

2s

512MB

2300

0%

Advanced Graph Problems

Тэдгээрийн хооронд $n$ хот, $m$ нислэгийн холболт бий. Аль ч хотоос аль ч хот руу явах боломжтой болгохын тулд шинэ нислэг нэм. Хамгийн багадаа хэдэн шинэ нислэг хэрэгтэй вэ?

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

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

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

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

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

Эхлээд $k$ бүхэл тоог хэвлэ: шаардлагатай шинэ нислэгийн тоо. Дараа нь шинэ нислэгүүдийг илэрхийлсэн $k$ мөр хэвлэ. Ямар ч хүчинтэй хариулт хэвлэж болно.

Хязгаарлалт

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

Жишээ

Оролт1

Гаралт1

1
4 2

0.1 / 64 KiB

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