#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);
}
}
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;
// for (int i = 0; i < n; i++)
// {
// int x = par(i);
// if (obd[x])
// continue;
// obd[x] = true;
// vector<int> dv;
// for (int j = 0; j < n; j++)
// {
// if (p[x][j] == 2)
// {
// // if (par(x) == par(j))
// // return 0;
// zd(x, j, false);
// dv.push_back(j);
// }
// }
// vector<int>& vsi = el[i];
// for (int k = 1; k < vsi.size(); k++)
// {
// int cnt = 0;
// for (int j = 0; j < n; j++)
// {
// if (p[vsi[k]][j] == 2)
// {
// // if (par(vsi[k]) != par(j))
// // return 0;
// zd(vsi[k], j, false);
// cnt++;
// }
// }
// if (cnt != dv.size())
// return 0;
// }
// if (!dv.empty())
// {
// // if (dv.size() < 2)
// // return 0;
// gr[x][dv[0]] = 1;
// gr[dv[0]][x] = 1;
// dv.push_back(x);
// for (int k = 0; k < dv.size()-1; k++)
// gr[dv[k]][dv[k+1]] = gr[dv[k+1]][dv[k]] = 1;
// }
// }
build(gr);
return 1;
}
