Az S. 143. feladat (2020. április)

S. 143. Adott egy irányított gráf, amelynek \(\displaystyle N\) csúcsa és \(\displaystyle M\) éle van. Semelyik két csúcs közt sincs egynél több közvetlen él (iránytól függetlenül). Nevezzük körsétának a csúcsok egy olyan \(\displaystyle x_{1}, x_{2}, x_{n}\) sorozatát, ahol \(\displaystyle x_{1}=x_{n}\) és minden \(\displaystyle 1\le i\le n-1\) esetén létezik \(\displaystyle x_{i}\)-ből \(\displaystyle x_{i+1}\)-be mutató él, valamint a körséta során egy csúcson tetszőleges sokszor átmehetünk, de egy élen csak egyszer.

Legyen az ilyen körséták száma egy gráfban \(\displaystyle K\). Kérdés, hogy legföljebb hány irányított élt húzhatunk be a gráfba úgy, hogy a körséták száma továbbra is \(\displaystyle K\) legyen, és semelyik két csúcs között ne legyen egynél több közvetlen él (iránytól függetlenül). A csúcsokat 1-től indexeljük.

Bemenet: az első sor tartalmazza az \(\displaystyle N\) és \(\displaystyle M\) számot. A következő \(\displaystyle M\) sor mindegyike tartalmaz egy \(\displaystyle a_{i}\) és \(\displaystyle b_{i}\) számot, ami azt jelenti, hogy megy egy irányított él az \(\displaystyle a_{i}\) csúcsból a \(\displaystyle b_{i}\) csúcsba. Kimenet: adjuk meg a maximálisan behúzható élek számát.

Példa:

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

Értékelés: a pontok 50%-a kapható, ha \(\displaystyle N,M\le 100\).

Beküldendő egy s143.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ő 2020. május 11-én LEJÁRT.

Statisztika:

5 dolgozat érkezett.
10 pontot kapott:	Horcsin Bálint, Noszály Áron, Szente Péter, Varga 256 Péter.
5 pontot kapott:	1 versenyző.

A KöMaL 2020. áprilisi informatika feladatai