Хотын автобусны сүлжээг дараах байдлаар загварчилъя.

• Буудал бүр → нэг орой (node)
• Хоёр буудлын хооронд шууд зам байвал → ирмэг (edge)

Зарим буудлууд зөвхөн нэг л өөр буудалтай холбогдсон байдаг.
Ийм буудлыг навчит буудал (leaf node) гэж нэрлэнэ.

? Зорилго

? Graph-д байгаа навчит буудлуудын (degree = 1) тоог ол.

Оролт:

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

N M

• N — буудлын тоо
• M — замын тоо

Дараагийн M мөр бүрт:

u v

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

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

Гаралт:

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

? Навчит буудлуудын тоо

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

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

Дэд бодлого

Жишээ:

Оролт-1

4 3
1 2
2 3
3 4

Гаралт-1

2

Тайлбар

Degree:

• 1 → 1 (leaf)
• 2 → 2
• 3 → 2
• 4 → 1 (leaf)

? Хариу = 2

Оролт-2

5 0

Гаралт-2

0

Тайлбар

Ямар ч edge байхгүй → degree = 0
? leaf биш

Оролт

5 4
1 2
1 3
1 4
1 5

Гаралт

4

Тайлбар

• 1 → degree 4
• бусад → degree 1 → leaf

? Хариу = 4