Fişierul intrare/ieşire:fof.in, fof.outSursăONIS 2014, Runda 3
AutorVlad DutaAdăugată defmins123FMI No Stress fmins123
Timp execuţie pe test0.25 secLimită de memorie5120 kbytes
Scorul tăuN/ADificultateN/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.infof.out
3 2
2 1
2 3
3
 
1
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content