#include <iostream>
#include <string>
#include <sstream>

#define M 20

using namespace std;

bool esBipartito(int n, int [][M]);
void mostrarMatriz(int mAdyacencia[][M], int nVertices);

int main(){
    int nVertices;              /* Numero de vertices */
    int mAdyacencia[M][M];      /* Matriz de Adyacencia */
    bool res;
    string s;

    cout << "Taller 2 - Grafo Bipartido" << endl;
    cout << "Nota: Las matrices se llenan por filas!" << endl << endl;

    while (1){
        cout << "Vertices: "; cin >> s;

        /* Convertir string a entero */
        istringstream convert(s);

        if (convert >> nVertices){
            break;
          }
      }

    cout << endl << "Llenar matriz de adyacencia con 1's o 0's" << endl << endl;;

    for(int i = 0; i < nVertices; i++){
        for (int j = 0; j < nVertices; j++){
            cout <<"[" << i + 1 << "," << j+1 << "]: "; cin >> mAdyacencia[i][j];
        }
    }

    mostrarMatriz(mAdyacencia, nVertices);

    res = esBipartito(nVertices, mAdyacencia);

    if(res == true)
        cout << endl << "Grafo bipartito!" << endl;
    else{ cout << endl << "Grafo NO bipartito!" << endl; }

    cin.sync();
    cin.get();

    return 0;
}

bool esBipartito(int nVertices, int mAdyacencia[][M]){
     int clase[M];

     clase[0] = 0;

     if(mAdyacencia[0][1] == 0)
          clase[1] = 0;
     else{
          clase[1] = 1;
     }

     for(int i = 2; i < nVertices; i++){
          if(mAdyacencia[0][i] == 0)
                clase[i] = 0;
          else{
                clase[i] = 1;
          }
          for(int j = 1; j <= i-1; j++){
                if(clase[i] == clase[j] && mAdyacencia[i][j] == 1)
                        return false;
          }
     }

     return true;
}

void mostrarMatriz(int mAdyacencia[][M], int nVertices){
    for (int i = 0; i < nVertices; i++){
        cout << endl;

        for (int j = 0; j < nVertices; j++) cout << " " << mAdyacencia[i][j];
    }

    cout << endl;
}