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 S. 88. feladat (2014. március)

S. 88. Adott egy irányítatlan gráf \(\displaystyle N\) (\(\displaystyle 1 \le N \le 100\;000\)) csúccsal és \(\displaystyle M\) (\(\displaystyle 1 \le M< N\)) éllel. Számítsuk ki, hogy hányféleképpen lehet az éleket úgy irányítani, hogy minden csúcsból legfeljebb egy él induljon ki. Adjuk meg ennek a számnak az 1000000007-tel vett osztási maradékát.

A program olvassa be a standard input első sorából \(\displaystyle N\)-et és \(\displaystyle M\)-et, majd a következő \(\displaystyle M\) sorból az \(\displaystyle a_i\), \(\displaystyle b_i\) (\(\displaystyle 1 \le a_i, b_i \le N\)) szóközzel elválasztott egészeket, melyek mindegyike egy-egy irányítatlan él két végpontját jelöli. Mivel a gráf nem feltétlenül egyszerű, ezért ugyanaz a számpár többször is szerepelhet a bemenetben. Írjuk a standard output első és egyetlen sorába a lehetőségek számát modulo 1000000007.

Pontozás és korlátok: A programhoz mellékelt, a helyes megoldás elvét tömören, de érthetően leíró dokumentáció 1 pontot ér. A programra akkor kapható meg a további 9 pont, ha bármilyen hibátlan bemenetet képes megoldani az 1 mp futásidőkorláton belül.

Részpontszámok a következőkre kaphatóak:

\(\displaystyle \bullet\) a program \(\displaystyle N\le 200\)-ra megoldást ad;

\(\displaystyle \bullet\) a program \(\displaystyle N\le 5000\)-re megoldást ad.

Beküldendő egy tömörített s88.zip állományban a program forráskódja (s88.pas, s88.cpp, ...) az .exe és más, a fordító által generált állományok nélkül, valamint a program rövid dokumentációja (s88.txt, s88.pdf, ...), amely a fentieken túl megadja, hogy a forrás mely fejlesztői környezetben fordítható.

(10 pont)

A beküldési határidő 2014. április 10-én LEJÁRT.


Mintamegoldásnak Makk László megoldását tesszük közzé. Oda kellett figyelni arra, hogy a gráfban lehetnek hurokélek is! s88.zip


Statisztika:

12 dolgozat érkezett.
10 pontot kapott:Makk László, Somogyvári Kristóf, Weisz Ambrus, Zalavári Márton.
9 pontot kapott:Alexy Marcell.
8 pontot kapott:1 versenyző.
6 pontot kapott:1 versenyző.
4 pontot kapott:1 versenyző.
3 pontot kapott:2 versenyző.
2 pontot kapott:1 versenyző.
0 pontot kapott:1 versenyző.

A KöMaL 2014. márciusi informatika feladatai