#include "supertrees.h"
#include <vector>
const int mxN = 1000;
int parent[mxN];
int rank[mxN];
int find(int x)
{
if(parent[x] == -1)
parent[x] = x;
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
bool merge(int x, int y)
{
int xRoot = find(x), yRoot = find(y);
if (xRoot == yRoot)
return false;
if (rank[xRoot] < rank[yRoot])
parent[xRoot] = yRoot;
else if (rank[yRoot] < rank[xRoot])
parent[yRoot] = xRoot;
else
{
parent[yRoot] = xRoot;
rank[xRoot] = rank[xRoot] + 1;
}
return true;
}
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
std::vector<std::vector<int>> answer;
for (int i = 0; i < n; i++) {
std::vector<int> row;
row.resize(n);
answer.push_back(row);
}
for(int i = 0; i < n; ++i){
parent[i] = i;
}
for(int i = 0; i < n; ++i){
for(int j = i + 1; j < n; ++j){
if(!p[i][j] && find(i) == find(j)){
return 0;
}
if(p[i][j]) merge(i, j);
}
}
for(int i = 0; i < n; ++i){
for(int j = i + 1; j < n; ++j){
if(!p[i][j] && find(i) == find(j)) return 0;
}
}
for(int i = 0; i < n; ++i){
int rep = find(i);
if(rep == i) continue;
answer[rep][i] = 1;
answer[i][rep] = 1;
}
build(answer);
return 1;
}
