#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
int fd_root(int a, int par[])
{
if(par[a] == a)
return a;
par[a] = par[par[a]];
return fd_root(par[a], par);
}
void merge(int a, int b, int par[])
{
a = fd_root(a, par);
b = fd_root(b, par);
//cout<<a<<b<<endl;
par[a] = b;
}
int construct(vector < vector <int> > p)
{
int n = p.size();
vector < vector <int> > edge;
vector <int> empty;
for(int i = 0; i<n; i++)
{
edge.push_back(empty);
for(int j = 0; j<n; j++)
{
edge[i].push_back(0);
}
}
int clpar[n], farpar[n];
for(int i = 0; i<n; i++)
{
clpar[i] = i;
farpar[i] = i;
}
for(int i = 0; i<n; i++)
{
for(int j = 0; j<n; j++)
{
if(p[i][j] != 0)
merge(i, j, farpar);
if(p[i][j] == 1)
merge(i, j, clpar);
}
}
bool possible = true;
for(int i = 0; i<n; i++)
{
for(int j = 0; j<n; j++)
{
if(fd_root(i, clpar) == fd_root(j, clpar) && p[i][j] != 1)
possible = false;
if(fd_root(i, farpar) == fd_root(j, farpar) && p[i][j] == 0)
possible = false;
}
}
if(!possible)
return 0;
for(int i = 0; i<n; i++)
{
if(clpar[i] != i)
{
edge[i][clpar[i]] = 1;
edge[clpar[i]][i] = 1;
}
}
vector <int> cycle[n];
for(int i = 0; i<n; i++)
{
if(clpar[i] == i)
{
cycle[farpar[i]].push_back(i);
}
}
int u, v, z;
for(int i = 0; i<n; i++)
{
if(farpar[i] == i)
{
if(cycle[i].size() == 2)
possible = false;
if(cycle[i].size() > 2)
{
z = cycle[i].size();
for(int j = 0; j<z-1; j++)
{
u = cycle[i][j];
v = cycle[i][j+1];
edge[u][v] = 1;
edge[v][u] = 1;
}
u = cycle[i][0];
v = cycle[i][z-1];
edge[u][v] = 1;
edge[v][u] = 1;
}
}
}
if(!possible)
return 0;
build(edge);
return 1;
}
