#include "supertrees.h"
#include <vector>
#include <set>
using namespace std;
int cpar[1005];
int tpar[1005];
vector<int> byTree[1005];
int tfind(int x)
{
if (tpar[x] == x)
return x;
return tpar[x] = tfind(tpar[x]);
}
void tmerge(int x, int y)
{
x = tfind(x);
y = tfind(y);
tpar[x] = y;
}
int cfind(int x)
{
if (cpar[x] == x)
return x;
return cpar[x] = cfind(cpar[x]);
}
void cmerge(int x, int y)
{
x = cfind(x);
y = cfind(y);
cpar[x] = y;
}
int construct(vector<vector<int>> p)
{
int n = p.size();
for (int i = 0; i < n; i++)
cpar[i] = tpar[i] = i;
vector<vector<int>> answer;
for (int i = 0; i < n; i++)
{
vector<int> row;
row.resize(n);
answer.push_back(row);
}
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
if (p[i][j] == 0)
continue;
if (p[i][j] == 1)
{
if (tfind(i) == tfind(j))
continue;
tmerge(i, j);
answer[i][j] = answer[j][i] = 1;
continue;
}
if (p[i][j] == 2)
cmerge(i, j);
}
}
for (int i = 0; i < n; i++)
{
byTree[tfind(i)].push_back(i);
for (int j = 0; j < n; j++)
{
if (p[i][j] != 0)
continue;
if (cfind(i) == cfind(j) || tfind(i) == tfind(j))
return 0;
}
}
for (int i = 0; i < n; i++)
{
if (cfind(i) != i)
continue;
vector<int> cs;
set<int> ts;
for (int j = 0; j < n; j++)
{
if (cfind(j) != i)
continue;
cs.push_back(j);
ts.insert(tfind(j));
}
vector<int> tv;
for (auto ti : ts)
{
tv.push_back(ti);
for (auto &x : byTree[ti])
for (auto &y : byTree[ti])
if (p[x][y] != 1)
return 0;
for (auto &tj : ts)
{
if (ti == tj)
continue;
for (auto &x : byTree[ti])
for (auto &y : byTree[tj])
if (p[x][y] != 2)
return 0;
}
}
int k = tv.size();
if (k < 2)
continue;
for (int x = 0; x < k; x++)
{
int nx = (x + 1) % k;
answer[tv[x]][tv[nx]] = answer[tv[nx]][tv[x]] = 1;
}
}
build(answer);
return 1;
}
