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 |