Fiecare element al unei matrice de adiacenta poate avea valoarea 1 sau 0. Deci "202 valori nenule" inseamna 202 valori de 1.
Orice element de pe linia i si coloana j al matricei de adiacenta are valoarea 1 daca nodurile i si j sunt adiacente sau valoarea 0 daca nodurile nu sunt adiacente.
Stiind ca graful este neorietat, relatia de adiacenta dintre noduri este reciproca (a[i][j] = a[j][i]). Astfel, o muchie intre noduri corespunde a doua valori de 1 in matricea de adiacenta.
202 valori nenule in matricea de adiacenta corespund pentru 101 muchii in graf.
Deci cerinta devine :
"Un graf neorientat cu 2021 de noduri are 101 muchii. Indicati numarul minim de componente conexe".
Pentru a avea un numar minim de componente conexe trebuie sa legam cat mai multe noduri folosind cat mai putine muchii. Astfel, legam cat mai multe noduri intr-o configuratie de arbore (arborele este cel mai eficient mod de a lega cat mai multe noduri cu cat mai putine muchii pentru ca nu exista cicluri).
Stim ca un arbore cu n+1 noduri poate fi alcatuit folosind n muchii.
Avand la dispozitie 101 muchii putem 'lega' un arbore cu 102 noduri. Acest arbore reprezinta o componenta conexa. Restul nodurilor sunt noduri izolate si fiecare reprezinta propria componenta conexa.
Cate noduri izolate avem : 2021-102 = 1919 de noduri izolate
Cate componente conexe avem : 1919 (pentru fiecare nod izolat) + 1 (pentru arbore) = 1920 componente conexe
