#include "supertrees.h"
#include <vector>
using namespace std;
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define MAX_N 1001
vector<int> linea[MAX_N]; // VECTOR PARA GUARDAR LOS NODOS DE CADA LINEA
int grupo[MAX_N]; // SUBGRAFO AL QUE PERTENECE CADA NODO
int construct(std::vector<std::vector<int> > p) {
int n = p.size();
rep(i, 0, n - 1) grupo[i] = i; // INICIALMENTE CADA NODO ESTÁ EN SU PROPIO GRUPO
rep(i, 0, n - 1){
rep(j, i + 1, n - 1){
if (p[i][j] == 0 && grupo[i] == grupo[j]) return 0; // LOS NODOS ESTAN DESCONECTADOS ENTRE ELLOS PERO PERTENECEN AL MISMO GRUPO
else if(p[i][j] == 1 && grupo[i] == i && grupo[j] == j){ // EL PRIMER QUE ENCUENTRAS DEL GRUPO LOS AGREGA TODOS A SU GRUPO
linea[i].push_back(j);
grupo[j] = i;
}
else if (p[i][j] == 1 && grupo[i] != grupo[j]) return 0; // SI ESTAN CONECTADOS Y NO ESTAN EN EL MISMO GRUPO EL SUBGRAFO ES INVALIDO
}
}
vector<vector<int> > respuesta;
rep(i, 0, n - 1){
vector<int> fila;
fila.resize(n);
respuesta.push_back(fila);
}
rep(i, 0, n - 1){
for(auto nodo : linea[i]){
respuesta[nodo][i] = 1;
respuesta[i][nodo] = 1;
}
}
build(respuesta);
return 1;
}
