#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 5;
#define pb push_back
struct UnionFind{
int parent[maxn], height[maxn];
void init(int n){
for(int i =0; i<n; i++) parent[i] =i;
memset(height, 0, sizeof height);
}
int root(int n){
if(parent[n]!= n)
parent[n] = root(parent[n]);
return parent[n];
}
bool same(int n1, int n2){
return root(n1) == root(n2);
}
void join(int n1, int n2){
int r1 = root(n1);
int r2 = root(n2);
if(height[r1]> height[r2]){
parent[r2] = r1;
height[r1] = max(height[r1]+1, height[r2]);
}
else{
parent[r1] = r2;
height[r2] = max(height[r2]+1, height[r1]);
}
}
};
int construct(vector<vector<int>> p) {
int n = p.size();
UnionFind uf;
uf.init(n);
for(int i =0; i<n-1 ; i++){
for(int j = i + 1; j<n; j++){
//cout<<i<<", "<<j<<endl;
if(p[i][j] > 0) uf.join(i, j);
}
}
map<int, set<int>> trees;
for(int i =0; i<n -1; i++){
for(int j =i + 1; j< n; j++){
if(p[i][j] == 0)
if(uf.same(i, j))return 0;
trees[uf.root(i)].insert(i);
trees[uf.root(j)].insert(j);
}
}
vector<vector<int>> ans(n, vector<int>(n, 0));
for(auto e : trees){
set<int> tree = e.second;
//cout << e.first<<endl;
vector<vector<int>> graph(tree.size(), vector<int>());
UnionFind uft;
uft.init(n);
vector<int> degree(n, 0);
//int endpoint;
for(int i : tree){
for(int j : tree){
if(i == j) continue;
//cout << i <<", "<<j<<endl;
if(p[i][j] ==1){
if(!uft.same(i, j)){
degree[i]++;
degree[j]++;
ans[i][j] = ans[j][i] =1;
uft.join(i, j);
}
}
}
}
}
build(ans);
return 1;
}
