#include "supertrees.h"
#include <vector>
using namespace std;
constexpr int maxn = 1010;
vector<vector<int>> ans;
int n;
struct DSU {
int pai[maxn], peso[maxn], ini[maxn];
DSU() { for(int i = 0; i < maxn; i++) pai[i] = ini[i] = i, peso[i] = 1; }
void init(const vector<int>& v) { for(const int& x : v) pai[x] = x, peso[x] = 1, ini[x] = x; }
int find(int x) { return pai[x] == x ? x : pai[x] = find(pai[x]); }
void join(int a, int b, bool ans_yes) {
a = find(a), b = find(b);
if(a == b) return;
if(peso[a] < peso[b])
swap(a, b);
if(ans_yes)
ans[ini[a]][b] = ans[b][ini[a]] = 1;
ini[a] = ini[b];
pai[b] = a;
peso[a] += peso[b];
}
} dsu;
vector<int> comp[maxn], comp2[maxn];
int connected_component(const vector<int>& ativos, const std::vector<std::vector<int>>& p) {
dsu.init(ativos);
for(int i : ativos) {
for(int j : ativos) {
if(p[i][j] == 1) dsu.join(i, j, 1);
}
}
vector<int> chains;
for(int i = 0; i < n; i++) {
if(dsu.find(i) == i) chains.push_back(i);
comp2[dsu.find(i)].push_back(i);
}
for(int i : ativos)
for(int x : comp2[i])
for(int y : comp2[i])
if(p[x][y] != 1) return 0;
if(chains.size() == 1) return 1;
if(chains.size() == 2) return 0;
// senao tenho q fazer o ciclo
int last = chains.back();
for(int x : chains)
ans[x][last] = ans[last][x] = 1, last = x; // junto todas as cabecas em um ciclo
return 1;
}
int construct(std::vector<std::vector<int>> p) {
n = p.size();
ans.assign(n, vector<int>(n, 0));
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(p[i][j] != 0) dsu.join(i, j, 0);
if(p[i][j] == 3) return 0;
}
}
for(int i = 0; i < n; i++)
comp[dsu.find(i)].push_back(i);
for(int i = 0; i < n; i++) {
for(int x : comp[i])
for(int y : comp[i])
if(p[x][y] == 0) return 0;
if(comp[i].size() && connected_component(comp[i], p) == 0) return 0;
}
build(ans);
return 1;
}
