Az S. 132. feladat (2019. február)

S. 132. Egy ország \(\displaystyle N\) városa között az elektromos energiát vezetékeken szállítják. Minden vezeték két várost köt össze, elektromos energiát előállító erőmű csak a 0 indexű városban van. Két várost több vezeték is összeköthet. Egy város akkor kap áramot, ha a vezetékekkel közvetlenül vagy közvetetten összeköttetésben van az erőművel. Egy vezeték nélkülözhetetlen, ha meghibásodásakor lesz olyan város, ami nem kap áramot.

Az országnak túl költséges karbantartani az összes vezetéket, ezért úgy döntenek, hogy \(\displaystyle Q\) darab vezetéket eltávolítanak a hálózatból. Kíváncsiak vagyunk, hogy kezdetben hány nélkülözhetetlen vezeték van, és hogy az egyes vezetékek eltávolításával mennyivel nő a nélkülözhetetlen vezetékek száma. A vezetékek eltávolítása során sosem lesz olyan város, ami nem kap áramot.

Bemenet: az első sorban a városok \(\displaystyle N\) száma, a vezetékek \(\displaystyle M\) száma és az eltávolítandó vezetékek \(\displaystyle Q\) száma található. A városokat és vezetékeket is 0-tól indexeljük. A következő \(\displaystyle M\) sor mindegyike két város indexét tartalmazza, amiket összeköt az adott vezeték. Az utolsó \(\displaystyle Q\) sor mindegyike egy vezeték indexét tartalmazza, amit eltávolítanak.

Kimenet: Az első sorba írjuk ki, hogy kezdetben hány nélkülözhetetlen vezeték van. A következő \(\displaystyle Q\) sorba pedig azt, hogy az egyes vezetékek eltávolításával mennyi lesz a nélkülözhetetlen vezetékek száma.

Példa:

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

Értékelés: a pontok 20% kapható, ha \(\displaystyle Q=0\)-ra ad jó megoldást; további 20%, ha \(\displaystyle Q\cdot M\le {10}^{6}\); további 10%, ha az eltávolítások során végig maximum 2 nélkülözhetetlen vezeték van; további 50% az eredeti bemenetre.

Beküldendő egy s132.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ő környezetben futtatható.

(10 pont)

A beküldési határidő 2019. március 11-én LEJÁRT.

Statisztika:

5 dolgozat érkezett.
10 pontot kapott:	Szente Péter.
4 pontot kapott:	3 versenyző.
1 pontot kapott:	1 versenyző.

A KöMaL 2019. februári informatika feladatai