#include "supertrees.h"
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
struct union_find{
vector<int> csop, mely;
void Init(int n){
csop.resize(n, -1);
mely.resize(n, 0);
return;
}
int Os(int a){
if(csop[a] == -1)
return a;
csop[a] = Os(csop[a]);
return csop[a];
}
bool Union(int a, int b)
{
a = Os(a);
b = Os(b);
if(a == b)
return false;
if(mely[a] < mely[b])
swap(a, b);
csop[b] = a;
mely[a] = max(mely[a], mely[b]+1);
return true;
}
};
vector<int> Halmaz(vector<int> &inds, union_find &csop, int c)
{
vector<int> ret;
for(int x : inds)
if(csop.Os(x) == c)
ret.push_back(x);
return ret;
}
int construct(vector<vector<int>> p) {
int n = p.size();
vector<vector<int>> answer(n, vector<int>(n, 0));
union_find csop;
csop.Init(n);
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if(p[i][j] == 3 || (i == j && p[i][j] != 1))
return 0;
for(int i = 0; i < n; i++)
{
for(int j = i+1; j < n; j++)
{
if(p[i][j] == 1)
{
int x = csop.Os(i), y = csop.Os(j);
if(csop.Union(x, y))
{
answer[x][y] = 1;
answer[y][x] = 1;
}
}
}
}
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(i == j)
continue;
if(csop.Os(i) == csop.Os(j) && p[i][j] != 1)
return 0;
}
}
vector<int> inds;
for(int i = 0; i < n; i++)
if(csop.Os(i) == i)
inds.push_back(i);
union_find csop2;
csop2.Init(n);
for(int i = 0; i < n; i++)
for(int j = i+1; j < n; j++)
if(p[i][j] == 2)
csop2.Union(csop.Os(i), csop.Os(j));
/*for(int i = 0; i < n; i++)
cout<<csop.Os(i)<<" ";
cout<<"\n";*/
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(i == j)
continue;
if(csop.Os(i) != csop.Os(j) && csop2.Os(csop.Os(i)) == csop2.Os(csop.Os(j)) && p[i][j] != 2)
return 0;
}
}
for(int i : inds)
{
if(csop2.Os(i) == i)
{
vector<int> v = Halmaz(inds, csop2, i);
if(v.size() == 1)
continue;
if(v.size() == 2)
return 0;
for(int j = 0; j < (int)v.size()-1; j++)
{
answer[v[j]][v[j+1]] = 1;
answer[v[j+1]][v[j]] = 1;
}
answer[v[0]][(*v.rbegin())] = 1;
answer[(*v.rbegin())][v[0]] = 1;
}
}
build(answer);
return 1;
}
