#include "supertrees.h"
#include <vector>
using namespace std;
#include <iostream>
bool debug=0;
#define dout if(debug)cout<<"# "
vector<int> head, tsize;
int query(int u){
// find the representative of u
if(head[u]==u)return u;
return head[u]=query(head[u]);
}
void do_union(int u, int v){ // union by size :)
if(tsize[query(v)] > tsize[query(u)]){
// add u to v
tsize[v] += tsize[u];
tsize[u] = 0;
head[query(v)] = query(u);
} else{
// add v to u
tsize[u] += tsize[v];
tsize[v] = 0;
head[query(u)] = query(v);
}
}
int construct(vector<vector<int>> p) {
int n = p.size();
// assume test case 2.
// initiate tsize and head
tsize = vector<int>(n, 1);
head = vector<int>(n);
for(int i=0; i<n; i++){
head[i]=i;
}
for(int y=0; y<n; y++){
for(int x=0; x<n; x++){
if(p[y][x]!=0 && p[y][x]!=1) return 0;
if(p[y][x]==1){
do_union(y,x);
}
}
}
// now go over everything again, and check if 2 unioned nodes have to be seperate. In this case, we return 0.
for(int y=0; y<n; y++){
for(int x=0; x<n; x++){
if(y==x && p[y][x] != 1)return 0;
else if(p[y][x] == 0 && query(y)==query(x)){
dout<<"no solution exists, because: \n";
dout<<"p["<<y<<"]["<<x<<"] = " << p[y][x]<<" = 0, and query("<<y<<")="<<query(y)<<" == query("<<x<<")="<<query(x)<<"\n";
return 0;
}
}
}
// now we know there exists a construction which meets the requirements
dout<<"there exists a valid solution.\n";
vector<vector<int>> answer(n, vector<int>(n,0));
for(int i=0; i<n; i++){
if(query(i) != i){
// this boy is connected to something!
answer[query(i)][i] = 1;
answer[i][query(i)] = 1;
}
}
build(answer);
return 1;
}
