| 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
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.
Cerinta
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
În fişierul de intrare linegraph.in pe prima linie se află un număr T, ce reprezintă numărul de teste din fişier. Pentru fiecare test pe prima linie se află două numere naturale N şi M separate prin spaţiu cu semnificaţiile din enunţ, iar pe următoarele M linii se află câte două numere separate prin spaţiu, ce reprezintă nodurile care au o muchie între ele.
Date de ieşire
În fişierul de ieşire linegraph.out pe prima linie trebuie să se afişeze fie cuvântul NU, dacă nu există un arbore asociat grafului dat, fie cuvântul DA, dacă există arbore asociat, şi în acest caz pe următoarea linie se va afişa un număr E, ce reprezintă numărul de noduri din arbore, şi pe următoarele E-1 linii se vor afişa câte două numere ce reprezintă perechile de noduri din arbore, care au o muchie între ele.
Restricţii
- 1 ≤ T ≤ 10.000
- 1 ≤ N ≤ 1.000
- 0 ≤ M ≤
- suma pătratelor tuturor N-urilor din fişierul de intrare nu depăşeşte 1.000.000;
- pentru teste în valoare de 15 puncte, se garantează că există soluţie şi că arborele din care s-a construit graful are fie formă de lanţ, fie are N-1 frunze;
- pentru alte teste în valoare de 55 de puncte, se garantează că N ≤ 100 şi suma pătratelor tuturor N-urilor din fişierul de intrare nu depăşeşte 10.000;
- dacă există mai multe soluţii, se poate afişa oricare dintre ele;
- arborele din fişierul de ieşire cu E noduri va avea nodurile numerotate cu 1,2,...,E;
- numerotarea efectivă a nodurilor din fişierul de ieşire nu este importantă – orice soluţie ce renumerotează nodurile va fi considerata un răspuns corect.
Exemplu
| linegraph.in | linegraph.out |
|---|---|
| 2 5 7 3 2 3 5 3 1 2 5 2 1 1 5 1 4 3 1 1 2 | DA 6 1 2 1 3 3 4 3 5 3 6 NU |
Explicaţie
În fişierul de intrare avem un graf. Fiecărei muchii dinacest graf îi corespunde un nod din arborele din fişierul de ieşire. Astfel: muchia (1,3) devine nodul 1, muchia (1,2) devine nodul 4, muchia (3,4) devine nodul 3, muchia (3,5) devine nodul 2 şi muchia (3,6) devine nodul 5.
Muchiile (1,3), (3,4), (3,5), (3,6) au toate nodul comun 3, deci nodurile lor corespunzătoare din graf (1,3,2,5) au toate muchii între ele.
În al doilea test nodul 3 este izolat şi graful nu poate proveni din niciun arbore.
