 |
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