#include "supertrees.h"
#include <bits/stdc++.h>
#define SZ(v) ((int)(v).size())
using namespace std;
using ll = long long;
struct UnionFind
{
vector<int> id;
UnionFind() {}
UnionFind(int N)
{
id.assign(N, -1);
}
int find(int u)
{
if (id[u] < 0) return u;
return id[u] = find(id[u]);
}
bool merge(int u, int v)
{
u = find(u), v = find(v);
if (u == v) return false;
if (id[u] > id[v]) swap(u, v);
id[u] += id[v];
id[v] = u;
return true;
}
vector<vector<int>> getComps()
{
vector<vector<int>> ret;
vector<vector<int>> comps(SZ(id));
for (int i(0); i < SZ(id); ++i)
comps[find(i)].push_back(i);
for (auto v : comps)
if (SZ(v))
ret.push_back(v);
return ret;
}
};
int construct(vector<vector<int>> p) {
int nbSommets = SZ(p);
vector<vector<int>> sol(nbSommets, vector<int>(nbSommets));
UnionFind uf(nbSommets);
for (int i(0); i < nbSommets; ++i)
for (int j(i+1); j < nbSommets; ++j)
if (p[i][j])
uf.merge(i, j);
for (int i(0); i < nbSommets; ++i)
for (int j(i+1); j < nbSommets; ++j)
if (uf.find(i) == uf.find(j) and p[i][j] == 0)
return 0;
for (int i(0); i < nbSommets; ++i)
if (uf.find(i) != i)
sol[uf.find(i)][i] = sol[i][uf.find(i)] = 1;
build(sol);
return 1;
}
