Монгол Улсын хотууд хоорондоо авто замаар холбогддог.

Хот бүрийг нэг орой (node),
хоёр хотын хооронд зам байвал ирмэг (edge) гэж үзье.

Одоогийн байдлаар зарим хотууд хоорондоо шууд болон дам замаар холбогдсон боловч бүх хотууд хоорондоо хүрч чаддаггүй байж магадгүй.

Засгийн газар дараах асуудлыг шийдэхийг хүсэж байна:

? Бүх хот хоорондоо хүрч болохуйц болгохын тулд хамгийн багадаа хэдэн шинэ зам барих хэрэгтэй вэ?

? Тайлбар

• Хэрэв хотууд аль хэдийн бүгд хоорондоо холбогдсон бол → 0 зам хэрэгтэй
• Үгүй бол зарим тусдаа хэсгүүдийг (component) хооронд нь холбох шаардлагатай

Оролт:

Эхний мөрөнд хоёр бүхэл тоо өгөгдөнө:

N M

• N — хотын тоо
• M — одоо байгаа замын тоо

Дараагийн M мөр бүрт хоёр бүхэл тоо өгөгдөнө:

u v

• u болон v хотын хооронд зам байна

? Энэ нь чиглэлгүй (undirected) граф

Гаралт:

Нэг бүхэл тоо хэвлэнэ:

• Бүх хотыг холбохын тулд шаардлагатай хамгийн бага шинэ замын тоо

Хязгаарлалтууд:

• 1 ≤ N ≤ 100000
• 0 ≤ M ≤ 100000
• 1 ≤ u, v ≤ N

Дэд бодлого

Жишээ:

Оролт-1

4 2
1 2
3 4

Гаралт-1

1

Тайлбар

Одоогийн байдлаар:

• 1 ↔ 2
• 3 ↔ 4

? 2 тусдаа хэсэг байна

? Тэднийг холбохын тулд:

- 1 зам нэмэхэд хангалттай

Оролт-2

5 0

Гаралт-2

4

Тайлбар

Бүх хот тусдаа байна:

? 5 хот → 5 component

? Холбохын тулд:

5 - 1 = 4 зам

Оролт-3

4 3
1 2
2 3
3 4

Гаралт-3

0

Тайлбар

Бүх хот аль хэдийн холбогдсон → шинэ зам хэрэггүй

? Нэмэлт тайлбар

Graph дээр:

? Хэрэв component-ийн тоо = K бол
? Бүх graph-ийг холбоход:

хамгийн бага зам = K - 1