#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define what_is(a) cout<< #a << " is " << a << "\n"
#define checker(a) cout << "checker reached " <<a << "\n"
const int maxn = 1000;
struct subset{
int parent,rank;
}subsets[maxn];
int find(int a){
if(subsets[a].parent==a)return a;
subsets[a].parent = find(subsets[a].parent);
return subsets[a].parent;
}
void Union(int a,int b){
a = find(subsets[a].parent),b = find(subsets[b].parent);
if(a==b)return;
if(subsets[a].rank<subsets[b].rank)
subsets[a].parent = b;
else if(subsets[a].rank>subsets[b].rank)
subsets[b].parent = a;
else{
subsets[a].parent = b;
subsets[b].rank++;
}
}
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
for(int i=0;i<n;i++)subsets[i] = {i,0};
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++){
if(p[i][j]==0)continue;
Union(i,j);
}
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
if(p[i][j]==0&&find(i)==find(j)){
return 0;
}
vector<vector<int>> sets(n,vector<int>());
for(int i=0;i<n;i++)
sets[find(i)].push_back(i);
vector<vector<int>> g(n,vector<int>());
for(int i=0;i<n;i++){
vector<int> vec(n,0);
g[i] = vec;
}
for(vector<int> st : sets){
if(st.size()<=1)continue;
for(int i=0;i<(int)st.size()-1;i++)
g[st[i]][st[i+1]] = g[st[i+1]][st[i]] = 1;
}
build(g);
return 1;
}
