#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;
}
}
};
int cntt;
std::vector<std::vector<int>> g;
std::vector<bool> used;
std::vector<std::vector<int>> answer;
void dfs(int v , int &ff) {
used[v] = true;
cntt++;
for(auto to : g[v]) {
if(!used[to]) {
answer[v][to] = true;
answer[to][v] = true;
dfs(to , ff);
return ;
}
}
if(v != ff) {
answer[v][ff] = true;
answer[ff][v] = true;
}
}
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if(p[i][j] != p[j][i]) return false;
}
}
used.assign(n , false);
g.resize(n);
answer.assign(n , std::vector<int>(n , false));
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);
g[i].push_back(j);
}
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if(!p[i][j]) {
if(t.Find(i) == t.Find(j)) return false;
}
}
}
for (int i = 0; i < n; i++)
{
if(!used[i] && p[i][i]) {
cntt = 0;
dfs(i , i);
// if(cntt <= 1) {
// return false;
// }
} else {
int cntt = -t.par[t.Find(i)];
if(!used[i] && cntt > 1) {
return false;
}
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if(answer[i][j] != answer[j][i]) return false;
}
}
build(answer);
return 1;
}
/*
4
2 0 2 2
2 0 2 2
2 2 2 2
0 0 0 0
3
2 2 2
2 2 2
2 2 2
3
2 2 0
2 2 0
0 0 0
*/
