diff --git a/Projet/Propagatio.cc b/Projet/Propagatio.cc index 557f457..a3292a0 100644 --- a/Projet/Propagatio.cc +++ b/Projet/Propagatio.cc @@ -1,84 +1,110 @@ #include #include +#include using namespace std; const string P1("P1 missing or incorrect"); const string WRONG_NB_COL_LGN("Nb columns and/or nb lines incorrect"); const string MATRIX_SQUARE("Matrix is not square"); const string IRREGULAR_CONTENT("Matrix description with incorrect content"); const string DISCONNECTED_GRAPH("Matrix corresponds to a disconnected graph"); void check_bpm(int &n); void check_bpm(int &n) { string header; // cout << "Header P1 ?" << endl; cin >> header; if (header != "P1") { cout << P1 << endl; exit(0); } int c,l; // cout << "Nombre de colonnes ?" << endl; cin >> c; // cout << "Nombre de lignes ?" << endl; cin >> l; if (l == c) n=l; else { cout << MATRIX_SQUARE << endl; exit(0); } + if (n == 0) + exit(0); } void make_adj(int n,vector> &tab); void make_adj(int n,vector> &tab) { for (int i(0); i < n; i++) { char c; int j(0); cin >> c; while(c != '\n') { if (c == '0' || c == '1') { tab[i][j]=int(c)-int('0'); j++; } else if (isspace(c)) { } else { cout << IRREGULAR_CONTENT << endl; exit(0); } cin.get(c); } if (j != n) { cout << WRONG_NB_COL_LGN << endl; exit(0); } tab[i][i]=0; } for (int i(0); i < n; i++) { for (int j(0); j < n; j++) { if (tab[i][j] == 1) tab[j][i]=1; } } } +void explore(int n,vector> &mat, vector &visited, int l); +void explore(int n,vector> &mat, vector &visited, int l) { + visited[l]=1; + for (int c(0); c < n; c++) { + if (visited[c] == 0 && mat[l][c] == 1) + explore(n,mat,visited,c); + } +} + + +void connectck(int n, vector &visited); +void connectck(int n, vector &visited) { + if (accumulate(visited.begin(),visited.end(),0) != n) { + cout << DISCONNECTED_GRAPH << endl; + exit(0); + } +} + + int main() { int n; check_bpm(n); vector> matAdj(n, vector(n)); make_adj(n,matAdj); for (int i(0); i < n; i++) { for (int j(0); j < n; j++) { cout << matAdj[i][j] << " "; } cout << endl; } + vector visited(n); + explore(n,matAdj,visited,0); + connectck(n,visited); + return 0; }