#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int MXN = 1005;
vector<int> par(MXN), cycle, line[MXN];
vector<int> cycle_vertex;
int root(int i) {
while(i != par[par[i]]) {
par[i] = par[par[i]];
i = par[par[i]];
}
return i;
}
void mergeset(int a, int b) {
par[root(a)] = root(b);
}
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
std::vector<std::vector<int>> answer;
for (int i = 0; i < n; i++) {
std::vector<int> row;
row.resize(n);
answer.push_back(row);
par[i] = i;
}
for(int i = 0; i < n; i++) {
int sum = 0;
for(int j = 0; j < n; j++) {
if(i == j) {
continue;
}
sum += p[i][j];
if(p[i][j] == 1) {
if(root(i) != root(j)) {
mergeset(i, j);
}
}
if(p[i][j] == 3) {
return 0;
}
}
if(sum == 0) {
par[i] = -1;
}
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(i == j || par[i] == -1 || par[j] == -1) continue;
if(p[i][j] == 0 && root(i) == root(j)) {
return 0;
}
}
}
for(int i = 0; i < n; i++) {
if(par[i] != -1) {
line[root(i)].push_back(i);
}
}
for(int i = 0; i < n; i++) {
int sz = line[i].size();
if(sz) {
cycle_vertex.push_back(line[i][0]);
}
for(int j = 0; j < sz - 1; j++) {
answer[line[i][j]][line[i][j + 1]] = 1;
answer[line[i][j + 1]][line[i][j]] = 1;
}
}
int sz = cycle_vertex.size();
if(sz >= 3) {
cycle_vertex.push_back(cycle_vertex[0]);
for(int i = 0; i < sz; i++) {
answer[cycle_vertex[i]][cycle_vertex[i + 1]] = 1;
answer[cycle_vertex[i + 1]][cycle_vertex[i]] = 1;
}
} else if(sz == 2) {
return 0;
}
build(answer);
return 1;
}
