#include "supertrees.h"
#include <vector>
#include <iostream>
const int NMAX = 1000;
std::vector <std::pair <int, int> > edges;
std::vector <std::vector <int>> input;
int N;
std::vector <std::pair <int, int>> g[NMAX + 1];
bool seen[NMAX + 1];
int nrComp;
std::vector <int> comp[NMAX + 1];
void dfsComp(int node)
{
seen[node] = true;
comp[nrComp].push_back(node);
for(auto it : g[node])
if(!seen[it.first])
dfsComp(it.first);
}
int kId, chainId[NMAX + 1];
std::vector < int > currentChain;
void dfs(int node, int par)
{
chainId[node] = kId;
currentChain.push_back(node);
if(par != -1)
edges.push_back({par, node});
for(auto it : g[node])
if(chainId[it.first] == 0 && it.second == 1)
dfs(it.first, node);
}
bool SolveComp(int c)
{
std::vector <int> representatives;
for(auto node : comp[c])
if(chainId[node] == 0)
{
++kId;
currentChain.clear();
dfs(node, -1);
representatives.push_back(currentChain[0]);
}
if((int)representatives.size() == 2)
return 0;
if((int)representatives.size() > 2)
{
for(int i = 1; i < (int)representatives.size(); i++)
edges.push_back({representatives[i], representatives[i - 1]});
edges.push_back({representatives[0], representatives.back()});
}
for(int i = 0; i < (int)comp[c].size(); i++)
for(int j = 0; j < (int)comp[c].size(); j++)
if(i != j)
{
if(chainId[comp[c][i]] != chainId[comp[c][j]])
{
if(input[comp[c][i]][comp[c][j]] != 2)
return false;
}
else
{
if(input[comp[c][i]][comp[c][j]] != 1)
return false;
}
}
return true;
}
int construct(std::vector<std::vector<int>> p) {
input = p;
N = p.size();
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
if(i != j && p[i][j] > 0)
{
if(p[i][j] == 3)
return 0;
g[i].push_back({j, p[i][j]});
}
for(int i = 0; i < N; i++)
if(!seen[i])
{
nrComp++;
dfsComp(i);
}
bool haveSol = true;
for(int i = 1; i <= nrComp; i++)
{
haveSol &= SolveComp(i);
if(!haveSol)
return 0;
}
std::vector<std::vector<int>> answer;
for (int i = 0; i < N; i++) {
std::vector<int> row;
row.resize(N);
answer.push_back(row);
}
for(auto it : edges)
answer[it.first][it.second] = answer[it.second][it.first] = 1;
build(answer);
return 1;
}
