#include "supertrees.h"
#include <vector>
#include <set>
using namespace std;
vector< vector<int> > answer;
vector< set<int> >nodos1, nodos2;
vector<int> padre1, padre2, row;
int n;
void init(){
nodos1.resize(n);
nodos2.resize(n);
padre1.resize(n);
padre2.resize(n);
row.resize(n);
for(int a=0;a<n;a++){
nodos1[a].insert(a);
nodos2[a].insert(a);
padre1[a] = a;
padre2[a] = a;
answer.push_back(row);
}
}
set<int> juntar(set<int> a, set<int> b){
set<int> :: iterator it = b.begin();
for(;it != b.end();it++){
a.insert(*it);
}
return a;
}
int buscar2(int a){
if(padre2[a] == a)return a;
return padre2[a] = buscar2(padre2[a]);
}
void unir2(int a, int b){
int A = buscar2(a);
int B = buscar2(b);
if(A != B){
padre2[max(A,B)] = min(A,B);
nodos2[min(A,B)] = juntar(nodos2[A], nodos2[B]);
nodos2[max(A,B)].clear();
}
}
int buscar1(int a){
if(padre1[a] == a)return a;
return padre1[a] = buscar1(padre1[a]);
}
void unir1(int a, int b){
int A = buscar1(a);
int B = buscar1(b);
if(A != B){
padre1[max(A,B)] = min(A,B);
nodos1[min(A,B)] = juntar(nodos1[A], nodos1[B]);
nodos1[max(A,B)].clear();
}
}
void crear2(){
for(int a=0;a<n;a++){
if(nodos2[a].size() > 1){
set<int>::iterator it = nodos2[a].begin();
int anterior = *it;
it++;
for(;it != nodos2[a].end();it++){
answer[anterior][*it] = 1;
answer[*it][anterior] = 1;
anterior = *it;
}
it--;
answer[*it][*nodos2[a].begin()] = 1;
answer[*nodos2[a].begin()][*it] = 1;
}
}
}
void crear1(){
for(int a=0;a<n;a++){
if(nodos1[a].size() > 1){
set<int>::iterator it = nodos1[a].begin();
int anterior = *it;
it++;
for(;it != nodos1[a].end();it++){
answer[anterior][*it] = 1;
answer[*it][anterior] = 1;
//anterior = *it;
}
}
}
}
int construct(vector<vector<int> > p) {
n = p.size();
init();
for(int a=0;a<n;a++){
for(int b=0;b<n;b++){
int val = p[a][b];
if(val == 0){
if(a == b)return 0;
}
if(val == 1){
unir1(a, b);
}
if(val == 2){
if(a == b)return 0;
unir2(a, b);
}
}
}
crear2();
crear1();
build(answer);
return 1;
}
