#include "supertrees.h" #include <bits/stdc++.h> using namespace std; vector<int> par; int fpar(int k){ if(par[k] == k){ return k; } par[k] = fpar(par[k]); return par[k]; } void merge(int k, int f){ k = fpar(k); f = fpar(f); par[k] = f; } int construct(vector<vector<int>> p) { int n = p.size(); par.resize(n); for(int i = 0; i < n; i++){ par[i] = i; } vector<std::vector<int>> answer(n, vector<int>(n)); for(int i = 0; i < n; i++){ for(int y = 0; y < n; y++){ if(i == y) continue; if(p[i][y] == 3){ return 0; } if(p[i][y] == 1){ if(fpar(i) == fpar(y)) continue; answer[i][y] = 1; answer[y][i] = 1; merge(i, y); } } } vector<bool> d(n); for(int i = 0; i < n; i++){ if(par[i] != i) continue; vector<int> j; for(int y = 0; y < n; y++){ if(i == y) continue; if(p[i][y] == 2){ j.push_back(par[y]); } } sort(j.begin(), j.end()); j.erase(unique(j.begin(), j.end()), j.end()); for(auto y : j){ d[y] = true; } j.push_back(i); if(j.size() == 2){ return 0; } if(j.size() == 1) continue; answer[j[0]][j.back()] = 1; answer[j.back()][j[0]] = 1; for(int y = 1; y < j.size(); y++){ answer[j[y]][j[y-1]] = 1; answer[j[y-1]][j[y]] = 1; } } // vector<vector<int>> checkz(n, vector<int>(n)); // if(checkz != p) return 0; build(answer); return 1; }