Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Az I/S. 65. feladat (2022. október)

I/S. 65. Adott egy \(\displaystyle N\) csúcsból és \(\displaystyle M\) élből álló irányítatlan gráf. A csúcsokat \(\displaystyle 1\)-től \(\displaystyle N\)-ig indexeljük. A gráfot az alábbi módon több lépésben bővítjük élek hozzáadásával: egy lépésben keresünk egy olyan \(\displaystyle x\) és \(\displaystyle y\) csúcspárt, amely nincs összekötve, de létezik olyan \(\displaystyle z\) csúcs, ami össze van kötve \(\displaystyle x\)-szel és \(\displaystyle y\)-nal is (\(\displaystyle 1\le x,y,z\le N\)). Ha találtunk ilyen \(\displaystyle x, y\) csúcspárt, akkor összekötjük őket egy éllel, ha nem, akkor befejeződött a gráf bővítése.

Adjuk meg, hogy a gráfbővítés befejeztével hány él van a gráfban. Mivel ez a szám nagyon nagy is lehet, ezért a szám \(\displaystyle (10^{9}+7)\)-tel vett osztási maradékát kell megadni.

A standard bemenet első sorában az \(\displaystyle N\) és \(\displaystyle M\) számok szerepelnek szóközzel elválasztva. A további \(\displaystyle M\) sor mindegyike 2 számot tartalmaz szóközzel elválasztva: egy adott él két végpontjának indexét.

A standard kimenet egyetlen sorában egy szám szerepeljen: a gráfbővítés befejeztével a gráfban levő élek száma modulo \(\displaystyle 10^{9}+7\).

Bemenet (a / jel sortörést helyettesít) Kimenet
8 5 / 1 2 / 2 4 / 3 2 / 6 7 / 7 8 9

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

Értékelés: a pontok 50%-a kapható, ha a program az \(\displaystyle N,M \le 500\) tesztesetekre helyes kimenetet ad.

(10 pont)

A beküldési határidő 2022. november 15-én LEJÁRT.


Statisztika:

8 dolgozat érkezett.
10 pontot kapott:Veres Benedek Zoltán, Zádor-Nagy Zsombor.
9 pontot kapott:Szabó Imre Bence.
5 pontot kapott:2 versenyző.
3 pontot kapott:1 versenyző.
2 pontot kapott:1 versenyző.
0 pontot kapott:1 versenyző.

A KöMaL 2022. októberi informatika feladatai