Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | linegraph.in, linegraph.out | Sursă | ONI 2019, clasele 11-12, ziua 2 |
| Autor | Andrei Constantinescu | Adăugată de |  Alex Luchianov •AlexandruLuchianov1 |
| Timp execuţie pe test | 0.35 sec | Limită de memorie | 512000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Linegraph
Poveste şi cerinţă...
Cătălin, după ce s-a jucat destul la bunici, a ajuns acasă, dar nu a venit cu mâna goală, ci a adus cu el cel mai frumos arbore pe care l-a avut în jocul “TreeGCD”, desenat pe o hârtie. Acasă, fratele lui mai mic a găsit această foaie şi s-a gândit să îşi încerce talentul la desen. El vrea să transforme arborele într-un graf în următorul fel: fiecare muchie din arborele iniţial devine un nod în noul graf, două noduri din noul graf sunt legate printr-o muchie dacă şi numai dacă cele două muchii corespunzătoare din arborele iniţial au un nod în comun.
După ce a construit acest graf, el a aruncat hârtia cu arborele iniţial. Când s-a întors de la şcoală, Cătălin, văzând ceea ce s-a întâmplat, nu a fost prea fericit. Din fericire, a aflat că voi puteţi să reconstruiţi arborele iniţial, dacă vă dă graful.
<h1>Cerinta</h1>
<b>Un text îngroşat</b>
Cerinţă
Se dau numărul N de noduri, numărul M de muchii şi cele M muchii din graf. Reconstruiţi arborele iniţial.
Este posibil ca fratele lui Cătălin să fi desenat greşit graful şi să nu existe un arbore asociat.
Date de intrare
Fişierul de intrare linegraph.in ...
Date de ieşire
În fişierul de ieşire linegraph.out ...
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| linegraph.in | linegraph.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
