Question

scrieti un program care sa verifice daca un graf este conex, folosind algoritmul de parcurgere in latime a grafului

Answer 1

#include <iostream>

using namespace std;

int main()

{

   bool matr_ad[32][32]{ true };

   int noduri, muchii;

   cin >> noduri >> muchii;

   for (int muchie = 0; muchie < muchii; muchie++) {

       int nodX, nodY;

       cin >> nodX >> nodY;

       matr_ad[nodX][nodY] = matr_ad[nodY][nodX] = true;

   }

   bool noduri_vizitate[32] = { false, true };

   int parcurgere[32] = { 0, 1 }, prim = 1, ultim = 1;

   while (prim <= ultim) {

       for (int nod = 1; nod <= noduri; nod++)

           if (matr_ad[parcurgere[prim]][nod] && !noduri_vizitate[nod]) {

               noduri_vizitate[nod] = true;

               parcurgere[++ultim] = nod;

           }

       prim++;

   }

   for (int nod = 1; nod <= noduri; nod++)

       if (!noduri_vizitate[nod]) {

           cout << "Graful nu este conex.";

           return 0;

       }

   cout << "Graful este conex.";

   return 0;

}