Az I/S. 62. feladat (2022. április)

I/S. 62. Egy országban \(\displaystyle N\) város található, és közöttük \(\displaystyle M\) darab kétirányú út vezet. Szeretnénk kiépíteni egy hálózatot úgy, hogy bizonyos városokba adótornyokat telepítünk (mindegyikbe legfeljebb egyet). A városokat 1-től \(\displaystyle N\)-ig indexeljük.

Egy út tökéletesen lefedett, ha pontosan az egyik végpont városába telepítünk adótornyot. Adjuk meg, hogy maximum hány adótornyot tudunk telepíteni úgy, hogy mind az \(\displaystyle M\) út tökéletesen legyen lefedve.

A bemenet első sorában az \(\displaystyle N\) és \(\displaystyle M\) számok találhatók szóközzel elválasztva. A következő \(\displaystyle M\) sor mindegyike két számot tartalmaz: egy adott várospár indexeit, amelyeket út köt össze.

A kimenet egyetlen sorában egy szám szerepeljen: maximum hány adótornyot tudunk telepíteni a feltételeknek megfelelően. Ha ez nem lehetséges, írjunk ki -1-et.

Magyarázat: telepítsünk adótornyot az 1, 3, 5 indexű városokba.

Korlátok: \(\displaystyle 1 \le N,M \le 10^{5}\). Időlimit: 0,4 mp.

Értékelés: a pontok 50%-a kapható, ha az \(\displaystyle 1 \le N, M \le 10\) feltételek esetén a program helyes kimenetet ad.

Beküldendő egy is62.zip tömörített állományban a megfelelően dokumentált és kommentezett forrásprogram, amely tartalmazza a megoldás lépéseit, valamint megadja, hogy a program melyik fejlesztői környezetben futtatható.

(10 pont)

A beküldési határidő 2022. május 16-án LEJÁRT.

Statisztika:

7 dolgozat érkezett.
10 pontot kapott:	Veres Benedek Zoltán.
9 pontot kapott:	Kovács Alex.
8 pontot kapott:	2 versenyző.
6 pontot kapott:	1 versenyző.
2 pontot kapott:	2 versenyző.

A KöMaL 2022. áprilisi informatika feladatai