Grafuri neorientate — cerință cu răspuns dezvoltat

Primele întrebări

1. Fișierul text graf.in descrie un graf neorientat. Pe prima linie se află două numere naturale nenule n și m, despărțite printr-un spațiu, cu n cel mult 100, reprezentând numărul de vârfuri, respectiv numărul de muchii. Vârfurile sunt numerotate de la 1 la n. Pe fiecare dintre următoarele m linii se află câte două numere naturale x și y, despărțite printr-un spațiu, reprezentând o muchie a grafului. Graful nu are muchii repetate și niciun vârf nu este unit cu el însuși.

   Scrie un program în limbajul C++ care citește datele din fișier, memorează graful prin matricea de adiacență și afișează pe ecran:

   • pe prima linie, gradele vârfurilor 1, 2, …, n, în această ordine, despărțite prin câte un spațiu;
   • pe a doua linie, numărul componentelor conexe ale grafului.

   De exemplu, dacă graf.in conține

   6 5
   1 2
   2 3
   1 3
   4 5
   5 6

   atunci programul afișează

   2 2 2 1 2 1
   2

   În rezolvare, explică pe scurt cum ai reținut graful, cum ai obținut gradele și ce metodă ai folosit pentru numărarea componentelor conexe. Programul trebuie să funcționeze pentru orice date de intrare care respectă enunțul, inclusiv atunci când graful are vârfuri izolate.