Question

Intrebarea e chiar lunga, sper sa ma ajute cineva. Chiar daca nu stie sa o faca toata, cine stie C++ si vrea sa ma ajute sau sa-mi dea o idee, sa-mi scrie, as fi foarte recunoscatoare!
Ionuț tocmai a terminat liceul și susține examenul de admitere la facultate. Știind că s-a pregătit
foarte bine pentru examen, el dorește să își anunțe reușita după examen printr-o postare pe Facebook.
Iounț cunoaște n utilizatori reprezentați de numerele de la 1 la n, între care există m relații de prietenie
de forma i j, unde i și j sunt utilizatori, iar n și m sunt numere naturale nenule. Un utilizator nu poate fi
prieten cu el însuși, iar o relație de prietenie între doi utilizatori ne spune că fiecare dintre ei este prieten
cu celălalt.
Întrucât dorește ca postarea lui să fie cât mai răspândită, Ionuț vrea să afle care sunt utilizatorii
cei mai bine conectați din mulțimea sa de cunoscuți, pentru ca eventual să le ceară prietenia. Pentru
aceasta, Ionuț trebuie să găsească cea mai mare submulțime de utilizatori cunoscuți, în care fiecare
utilizator din această submulțime are cel puțin k prieteni aflați la rândul lor în submulțime, unde k este
un număr natural nenul.
Fiind date la intrare numerele n, m și k, pe aceeași linie, separate prin spațiu, precum și 2m
numere naturale cuprinse între 1 și n, pe o linie nouă, separate prin spațiu, reprezentând în ordine cele
m relații de prietenie între cei n utilizatori, ajutați-l pe Ionuț să găsească o soluție la problema sa,
rezolvând următoarele subpuncte:
a) Să se determine și să se afișeze, în ordine de la 1 la n, numărul de prieteni al fiecăruia dintre cei
n utilizatori, conform relațiilor de prietenie date.
b) Să se determine și să se afișeze, printr-o soluție de complexitate timp cât mai bună, în funcție de
datele de intrare, membrii celei mai mari submulțimi de utilizatori, cu proprietatea că fiecare
utilizator din această submulțime are cel puțin k prieteni aflați la rândul lor în submulțime. În
cazul în care nu există o astfel de submulțime pentru k dat, răspunsul va fi cuvântul NU.

Answer 1

Am fost obosit cand am facut programul acesta, deci s-ar putea sa fi scris explicatiile din cod ceva mai incoerent decat mi-as dori. Dar o sa incerc sa iti explic cum m-am gandit asa.

Am cautat enuntul pe Google, si am gasit problema impreuna cu niste exemple date. O sa ma folosesc de acele exemple pentru a explica modul in care am gandit problema.

In primul rand, din enuntul problemei ne dam seama ca o putem echivala cu un graf neorientat, in care cele n noduri sunt copii din reteaua Facebook si cele m muchii sunt cele m relatii neorientate descrise in vectorul de 2m elemente.

Orice graf neorientat poate fi reprezentat printr-o matrice de adiacenta: o matrice de dimensiuni de n linii si n coloana in care punem valoarea 0 pe pozitia (i,j) in cazul in care nu exista o muchie intre nodul i si nodul j
Astfel pentru cazul
5 5 2
1 2 5 1 3 2 4 5 1 4

matricea lui de adiacenta este:
0 1 0 1 1
1 0 1 0 0
0 1 0 0 0
1 0 0 0 1
1 0 0 1 0

observi ca pe prima linie 0 arata ca nodul 1 nu are muchie cu sine insusi, nodul 1, si nici cu nodul 3, dar este valoarea 1 pe pozitiile 2,4 si 5, ceea ce arata faptul ca exista muchiile 1-2 1-4 si 1-5 care intr-adevar exista dupa cum arata in text.

Acum sa vedem cerintele
a) cerinta poate fi echivalata cu gasirea tuturor gradului fiecarui nod, adica cu cate alte noduri se invecineaza(exista o muchie catre alt nod) adica cati prieteni are un copil. In cazul matricii de adiacenta, tot ce trebuie facut este sa fie adunate numarul de valori de 1 de pe fiecare linie.
Astfel, vedem ca nodul 1 are 3 vecini(prieteni) adica 2,4,5, nodul 2 are 2 prieteni(1,3) si asa mai departe. Doar aduni valorile pe fiecare linie
b) In primul rand,un nod nu va putea face parte din submultime, daca nu are un nr de prieteni cel putin egal cu numarul k impus
In cazul nostru, vectorul cu nr de prieteni, produce urmatoarele valori:

3 2 1 2 2

In acest caz, k=2. Deci stim deja ca nodul 3 nu poate fi in submultime, pentru ca are doar un singur prieten. Pentru a-l ignora, am putea sa il inlocuim cu o valoare care in mod clar nu reprezinta numarul de vecini/prieteni al nodului, precum -1 Atunci am avea
3 2 -1 2 2
Dar sirul nu reflecta adevarul pentru ca nu am exclus si relatiile de prietenie pe care le avea nodul 3: anume cea cu nodul 2. Nodul 2 inca apare cu 2 prieteni, desi noi am eliminat deja prietenul nod 3. Asadar, inainte sa-l marcam cu -1, scadem din nodul 2 valoarea de prieteni cu o valoare
3 1 -1 2 2
Acum parcurgem inca o data vectorul. Observam ca nodul 2 nu mai are suficienti prieteni, il marcam si scadem legatura cu nodul 1. Vectorul de prieteni va arata astfel
2 -1 -1 2 2
Acum observam ca toti sunt fie mai mari sau egal decat 2, fie i-am exclus din multimea de prieteni. Deci inseamna ca este o submultime in care sunt prieteni intre ei. Deci cea mai mare submultime posibila este formata din elementele 1,4 si 5.
Daca in schimb am avea k=3, la sfarsit am avea doar un vector de -1 pentru ca am fi nevoiti sa eliminam toate elementele
-1 -1 -1 -1 -1
In acest caz, nu exista o asemenea submultime
Iti atasez un fisier zip cu fisierul cpp sursa, textul de intrare si un text de iesire in care apare matricea de adiacenta a grafului. Rezultatele cerute sunt afisate pe ecran cu cout. Exemplul dat in fisiere este al treilea din acel sir care apare in pdful cu subiectele
http://fmi.unibuc.ro/ro/pdf/2016/admitere/licenta/Subiecte_DL_INFO_iulie_2016.pdf

5e9cabc58c06191e2921d993121393aa.cpp

40b05272820767d704363a4d0510a555.txt