#include "supertrees.h"
#include <vector>
#include <iostream>
using namespace std;
vector<vector<int>> answer;
#define nmax 1000
int daddy[nmax];
int find_daddy( int a ) {
int x;
if( daddy[a] == a )
return a;
x = find_daddy( daddy[a] );
daddy[a] = x;
return x;
}
void marry_daddy( int a, int b ) {
int x, y;
x = find_daddy( a );
y = find_daddy( b );
daddy[x] = y;
}
int construct( vector<vector<int>> p) {
int n = p.size();
for (int i = 0; i < n; i++) {
vector<int> row;
row.resize(n);
answer.push_back(row);
}
int i, j;
bool ok = true;
for( i = 0; i < n; i++ )
daddy[i] = i;
for( i = 0; i < n; i++ ) {
for( j = 0; j < n; j++ )
if( p[i][j] > 0 )
marry_daddy( i, j );
}
for( i = 0; i < n; i++ ) {
for( j = 0; j < n; j++ )
if( p[i][j] == 0 && find_daddy(i) == find_daddy(j) )
ok = false;
}
if( !ok )
return 0;
for( i = 0; i < n; i++ )
if( find_daddy(i) != i ) {
answer[i][find_daddy(i)] = 1;
answer[find_daddy(i)][i] = 1;
}
build(answer);
return 1;
}
