#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
struct dsu{
vector<int> pad,tam;
int find(int a){return (a==pad[a])?a:pad[a]=find(pad[a]);}
bool unite(int a,int b){
if((a=find(a))==(b=find(b)))return false;
if(tam[a]<tam[b])swap(a,b);
tam[pad[b]=a]+=tam[b];
return true;
}
dsu(int n){
pad.resize(n);
tam.resize(n);
for(int i=0;i<n;i++)tam[pad[i]=i]=1;
}
};
int construct(vector<vector<int>> p){
int n=p.size();
vector<vector<int>> answer(n,vector<int>(n));
//vector<bool> esciclo(n);
// si p=3, entonces no hay solucion porque tenemos que tener 2 ciclos:
// 0-1,1-3,0-2,2-3,0-3, pero entonces hay 4 caminos e 1 a 2
dsu clave(n);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(p[i][j]==3)return 0;
// si es 0 pertenecen a diferentes componentes
if(p[i][j])clave.unite(i,j);
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(!p[i][j] && clave.find(i)==clave.find(j))return 0;
}
}
// no puede haber 2 ciclos en un mismo componente sino habria >=4 caminos de a a b
// -> cada componente hay a lo mucho un ciclo, y los demas conectan al ciclo
for(int i=0;i<n;i++){
vector<int> componentes;
for(int j=0;j<n;j++)if(clave.find(j)==i)componentes.push_back(j);
// resolver cada componente
// si el nodo tiene todo 2,0 y el mismo 1 entonces pertenece al ciclo
if(componentes.size()<=1)continue;
/*vector<int> parteciclo;
for(auto u:componentes){
int con[3]={0,0,0};
for(int j=0;j<componentes.size();j++){
con[p[u][componentes[j]]]++;
}
if(con[1]==1){
parteciclo.push_back(u);
esciclo[u]=true;
}
}
if(parteciclo.empty()){
// es un tree;
for(int j=1;j<componentes.size();j++){
answer[componentes[j-1]][componentes[j]]=answer[componentes[j]][componentes[j-1]]=1;
}
continue;
}
//if(parteciclo.size()<=2)return 0;
// los ciclos se unen
for(int j=1;j<parteciclo.size();j++){
answer[parteciclo[j-1]][parteciclo[j]]=answer[parteciclo[j]][parteciclo[j-1]]=1;
}
answer[parteciclo[0]][parteciclo.back()]=answer[parteciclo.back()][parteciclo[0]]=1;*/
// si dos tiene 1 solo camino, entonces estan en el mismo lado
/*cout << endl << endl;
for(auto u:componentes){
cout << u << ' ';
}
cout << endl << endl;*/
dsu subdsu(n);
for(int j=0;j<componentes.size();j++){
//if(esciclo[componentes[j]])continue;
for(int k=j+1;k<componentes.size();k++){
//if(esciclo[componentes[k]])continue;
if(p[componentes[j]][componentes[k]]==1){
if(subdsu.unite(componentes[j],componentes[k])){
answer[componentes[j]][componentes[k]]=answer[componentes[k]][componentes[j]]=1;
//cout << componentes[j] << ' ' << componentes[k] << endl << endl;
}
}
}
}
// si hay un par que tienen 2 caminos pero pertenecen al mismo lado, entonces es imposible
for(int j=0;j<componentes.size();j++){
//if(esciclo[componentes[j]])continue;
for(int k=j+1;k<componentes.size();k++){
//if(esciclo[componentes[k]])continue;
if(p[componentes[j]][componentes[k]]==2 && subdsu.find(componentes[j])==subdsu.find(componentes[k]))return 0;
}
}
// cuantos subcomponentes hay?
vector<int> subcomponentes;
for(int j=0;j<componentes.size();j++){
//if(esciclo[componentes[j]])continue;
if(subdsu.find(componentes[j])==componentes[j])subcomponentes.push_back(componentes[j]);
}
// los jefes de cada subcomponente se conecta
for(int j=1;j<subcomponentes.size();j++){
answer[subcomponentes[j-1]][subcomponentes[j]]=answer[subcomponentes[j]][subcomponentes[j-1]]=1;
}
answer[subcomponentes[0]][subcomponentes.back()]=answer[subcomponentes.back()][subcomponentes[0]]=1;
/*if(subcomponentes.size()>parteciclo.size())return 0;
// cada subcomponente se conecta al ciclo
for(int j=0;j<subcomponentes.size();j++){
answer[subcomponentes[j]][parteciclo[j]]=answer[parteciclo[j]][subcomponentes[j]]=1;
}*/
}
build(answer);
return 1;
}
