#include "supertrees.h"
#include <vector>
using namespace std;
int find(vector<int>& link, int x) {
while (x != link[x]) {
x = link[x];
}
return x;
}
void join(vector<int>& link, vector<int>& sz, int a, int b) {
a = find(link, a);
b = find(link, b);
if (sz[a] < sz[b]) swap(a,b);
link[b] = a;
}
bool same(vector<int>& link, int a, int b) {
return find(link, a) == find(link,b);
}
int construct(vector<vector<int>> p) {
int n = p.size();
vector<vector<int>> answer(n, vector<int>(n));
vector<int> link(n);
vector<int> sz(n, 0);
for (int i = 0; i < n; i++) {
link[i] = i;
}
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
if (p[i][j] && !same(link, i, j)) {
join(link, sz, i,j);
answer[i][j] = 1;
answer[j][i] = 1;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
if (!p[i][j] && same(link, i, j)) {
return 0;
}
}
}
build(answer);
return 1;
}
