#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
const int mxN = 1005;
int par[mxN], depth[mxN];
vector<int> adj[mxN];
bool find(int x) {
return x == par[x] ? x : par[x] = find(par[x]);
}
void unite(int x, int y) {
x = find(x), y = find(y);
if(depth[x] > depth[y])
par[y] = x;
else if(depth[x] < depth[y])
par[x] = y;
else
par[y] = x, depth[x]++;
}
int construct(vector<vector<int> > p) {
int n = p.size();
for(int i = 0; i < n; i++)
par[i] = i, depth[i] = 1;
for(int i = 0; i < n-1; i++) {
for(int j = i+1; j < n; j++) {
if(p[i][j] == 1)
unite(i, j);
}
}
for(int i = 0; i < n; i++)
adj[find(i)].push_back(i);
for(int i = 0; i < n-1; i++) {
for(int j = i+1; j < n; j++) {
if(p[i][j] == 0 && find(i) == find(j))
return 0;
}
}
vector<vector<int> > b(n, vector<int>(n, 0));
for(int i = 0; i < n; i++) {
for(int j = 0; j < (int) adj[i].size()-1; j++) {
b[adj[i][j]][adj[i][j+1]] = 1;
b[adj[i][j+1]][adj[i][j]] = 1;
}
}
build(b);
return 1;
}
