#include "supertrees.h"
#include <vector>
#include <iostream>
using namespace std;
bool obd[20005];
int dis[20005];
vector<int> el[20005];
int par(int x)
{
return dis[x] = (dis[x] == x ? x : par(dis[x]));
}
void zd(int x, int y, bool zlij = true)
{
x = par(x);
y = par(y);
if (x == y)
return;
if (el[x].size() < el[y].size())
swap(x, y);
if (zlij)
{
for (auto e : el[y])
el[x].push_back(e);
}
el[y].clear();
dis[y] = x;
return;
}
int construct(vector<vector<int>> p)
{
int n = p.size();
vector<vector<int>> gr(n, vector<int>(n, 0));
for (int i = 0; i < n; i++)
{
el[i].push_back(i);
dis[i] = i;
}
for (int i = 0; i < n; i++)
for (int j = i+1; j < n; j++)
{
if (p[i][j] == 1 && par(i)-par(j))
{
gr[par(i)][par(j)] = gr[par(j)][par(i)] = 1;
zd(i, j, 0);
}
}
int dalje = 0;
for (int i = 0; i < n; i++)
for (int j = i+1; j < n; j++)
{
if (p[i][j] == 2 && par(i)-par(j))
{
dalje = 1;
zd(i, j);
}
}
if (dalje)
{
for (int i = 0; i < n; i++)
{
int x = par(i);
if (obd[x])
continue;
obd[x] = 1;
vector<int> tr = el[x];
// if (tr.size() <= 2)
// return 0;
tr.push_back(x);
int pr = -1;
for (auto v : el[x])
{
if (pr != -1)
gr[v][pr] = gr[pr][v] = 1;
pr = v;
}
}
}
for (int i = 0; i < n; i++)
for (int j = i+1; j < n; j++)
if (p[i][j] == 0 && par(i) == par(j))
return 0;
build(gr);
return 1;
}
