 |
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