#include "supertrees.h" #include <bits/stdc++.h> using namespace std; vector<int> par; vector<vector<int>> g; vector<bool> vis; vector<vector<int>> checkz; vector<bool> d; 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 cur = 0; void dfs(int k, bool cyc){ if(cyc){ checkz[cur][k] = 2; checkz[k][cur] = 2; }else{ checkz[cur][k] = 1; checkz[k][cur] = 1; } if(d[k] && k != cur){ cyc = true; } vis[k] = true; for(int y = 0; y < g[k].size(); y++){ if(vis[g[k][y]]) continue; dfs(g[k][y], cyc); } } 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); } } } d.clear(); d.resize(n); for(int i = 0; i < n; i++){ if(par[i] != i || d[i]) continue; vector<int> j; for(int y = 0; y < n; y++){ if(i == y) continue; if(p[i][y] == 2){ if(d[par[y]]) return 0; 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; } } checkz.clear(); checkz.resize(n, vector<int>(n)); g.resize(n); vis.resize(n); for(int i = 0; i < n; i++){ for(int y = 0; y < n; y++){ if(i == y) continue; if(answer[i][y] == 1){ g[i].push_back(y); } } } cur = 0; for(;cur < n; cur++){ vis.clear(); vis.resize(n); dfs(cur, false); checkz[cur][cur] = 1; } if(checkz != p) return 0; build(answer); return 1; }