#include "supertrees.h"
#include <vector>
#include <iostream>
struct DSU {
std::vector<int> par;
int n , components;
DSU(int _n) {
n = _n;
components = n;
par.assign(n , -1);
}
int Find(int u) {
if(par[u] < 0 ) return u;
return par[u] = Find(par[u]);
}
bool Union(int u , int v) {
u = Find(u);
v = Find(v);
if(u != v) {
components--;
if(par[u] > par[v]) {
par[v] += par[u];
par[u] = v;
return true;
}
par[u] += par[v];
par[v] = u;
return true;
} else {
return false;
}
}
};
std::vector<int> used;
std::vector<std::vector<int>> g;
std::vector<std::vector<int>> answer;
void dfs(int v) {
used[v] = true;
for(int &to : g[v]) {
if(!used[to]) {
answer[v][to] = true;
answer[to][v] = true;
dfs(to);
}
}
}
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
used.assign(n , false);
g.resize(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if(p[i][j] != p[j][i]) return false;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if(p[i][j]) {
g[i].push_back(j);
}
}
}
answer.assign(n , std::vector<int> (n , false));
for (int i = 0; i < n; i++)
{
if(!used[i]) {
dfs(i);
}
}
DSU t(n);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if(p[i][j]) t.Union(i , j);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if(!p[i][j]) {
// std::cerr << i << ':' << j << std::endl;
if(t.Find(i) == t.Find(j)) return false;
}
}
}
build(answer);
return 1;
}
