👤
IALEXANDRAMARIA10ZE
a fost răspuns

scrieti un program care sa determine toate componentele conexe ale unui graf, folosind algoritmul de parcurgere in latime a grafului

Răspuns :

#include <iostream>

#include <algorithm>

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 comp = 1, nod_comp = 1;

   while (nod_comp) {

       int parcurgere[32] = { 0, nod_comp }, 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++;

       }

       cout << "Componenta conexa " << comp++ << " : ";

       sort(parcurgere, parcurgere + ultim);

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

           cout << parcurgere[nod] << ' ';

       cout << '\n';

       nod_comp = 0;

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

           if (!noduri_vizitate[nod]) {

               nod_comp = nod;

               noduri_vizitate[nod] = true;

               break;

           }

   }

   return 0;

}

Vă mulțumim pentru vizita pe site-ul nostru dedicat Informatică. Sperăm că informațiile prezentate v-au fost utile. Dacă aveți întrebări sau aveți nevoie de suport suplimentar, nu ezitați să ne contactați. Ne bucurăm să vă revedem și vă invităm să ne adăugați în lista de favorite!


Ze Schools: Alte intrebari