Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | fof.in, fof.out | Sursă | ONIS 2014, Runda 3 |
| Autor | Vlad Duta | Adăugată de |  FMI No Stress •fmins123 |
| Timp execuţie pe test | 0.125 sec | Limită de memorie | 5120 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Friend of Friend
In reteaua de socializare hi6 fiecaruia dintre cei N utilizatori ii este asociat un id sub forma unui numar intreg. Spunem ca doi utilizatori sunt prieteni daca intre ei exista o relatie de prietenie in reteaua de socializare. Pentru a creste popularitatea retelei de socializare si a creste interactiunea utilizatorilor trebuie sa implementam un sistem prin care unui utilizator ii este afisata o lista de persoane pe care este foarte probabil sa le cunoasca si care ii sunt sugerate sprea adaugare la prieteni. Primul pas pentru a reusi acest lucru este de a genera pentru fiecare utilizator lista de persoane cu care nu este prieten, dar cu care are macar un prieten comun.
Date de intrare
Fişierul de intrare fof.in contine pe prima linie doua numere naturale N si M, reprezentand numarul de utilizatori, respectiv numarul de relatii de prietenie din reteaua hi6. Pe urmatoarele M numere sunt definite relatiile de prietenie, cate una pe linie, sub forma unei perechi de id-uri.
Date de ieşire
În fişierul de ieşire fof.out va contine N linii. Pe linia i, (1 ≤ i ≤ N) se va afisa lista de sugestii generata pentru utilizatorul care are id-ul i. Lista afisata va fi sortata descrescator dupa numarul de prieteni comuni, iar in caz de egalitate crescator dupa id.
Restricţii
- 1 ≤ N ≤ 1000
- 1 ≤ M ≤ 5000
- Toate id-urile sunt numere naturale distincte intre 1 si N
Exemplu
| fof.in | fof.out |
|---|---|
| 3 2 2 1 2 3 | 3 1 |
