Programozás‎ > ‎Feladatok‎ > ‎

Járvány

A H1N1 vírus megérkezett az országba, ezért oltóállomásokat kell felállítani, ahol a lakosok szakemberektől kaphatják meg a védőoltást. A költségvetés állapota gyászos, ezért minimalizálni kell az oltóállomások számát. Az elégséges szolgáltatáshoz viszont szükséges, hogy minden állampolgár eljuthasson egy oltóállomásra, viszonylag kevés utazással.
Az egészségügyi minisztérium a következő feltételekkel definiálta az elégséges szolgáltatást:
  • egy tetszőleges településen kell lennie állomásnak, VAGY
  • a településről közvetlen elérhető kell legyen egy olyan település, ahol van állomás.


A közvetlen elérés azt jelenti, hogy a két település között vezet út, ami nem halad át más településeken. 

Feladat

Határozzuk meg, hogy települések egy adott hálózatára legkevesebb hány oltóállomást kell telepíteni, az elégséges szolgáltatás biztosításához!

Bemenet

A bemenet első sora két számot tartalmaz: a települések számát (3<=N<=30) és a közvetlen utak számát (0<=M<=435). Ezután M sorban a közvetlen úttal összekötött települések sorszámai következnek, szóközzel elválasztva.

Kimenet

A kimenet egyetlen számot tartalmaz, a minimálisan szükséges oltóállomások számát.

Példa

Bemenet  Kimenet
8 12
1 2
1 6
1 8
2 3
2 6
3 4
3 5
4 5
4 7
5 6
6 7
6 8
2


Tesztadatok

Címkék

A feladat forrása: saját feladat
Algoritmusok: backtrack, visszalépéses keresés

megoldás