Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.1 kB
3
Indexable
Never
#include <iostream>
using namespace std;

const int MAX_N = 100; // mărimea maximă a matricei de adiacență
int a[MAX_N][MAX_N]; // matricea de adiacență
int t[MAX_N]; // vectorul de marcări
int n; // numărul de noduri

// procedura de parcurgere în adâncime
void pdf(int p) {
    cout << p << " ";
    t[p] = 1;
    for (int j = 1; j <= n; j++) {
        if (a[p][j] == 1 && t[j] == 0) {
            pdf(j);
        }
    }
}

int main() {
    // citim matricea de adiacență și numărul de noduri
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
        }
        t[i] = 0;
    }

    // parcurgem graful și afișăm componentele conexe
    bool gasit = false;
    do {
        gasit = false;
        int i = 1;
        while (i <= n && !gasit) {
            if (t[i] == 0) {
                gasit = true;
            }
            i++;
        }
        if (gasit) {
            cout << "Componenta conexa: ";
            pdf(i - 1);
            cout << endl;
        }
    } while (gasit);

    return 0;
}