#include <bits/stdc++.h> #include "supertrees.h" #include <vector> using namespace std; const int N = 1e3+5; int par[N]; int s[N]; vector <vector<int>> v(N); vector<vector<int>> answer; int getpar(int x) { if (x == par[x]) return x; return par[x] = getpar(par[x]); } void unionset(int a, int b) { a = getpar(a); b = getpar(b); if (a == b) { return; } par[a] = b; s[b] += s[a]; s[a] = 0; } void add(int x, int y) { answer[x][y] = answer[y][x] = 1; } int construct(vector<vector<int>> p) { int n = p.size(); for (int i = 0; i < n; i++) { vector<int> row(n,0); answer.push_back(row); } for (int i = 0; i < n; i++) s[i] = 1,par[i] = i; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (p[i][j] == 3) return 0; } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (p[i][j] == 1 && getpar(i) != getpar(j)) { unionset(i,j); add(i,j); } } } for (int i = 0; i < n; i++) { v[getpar(i)].push_back(i); } for (int i = 0; i < n; i++) { if (getpar(i) != i) continue; for (auto x:v[i]) { for (auto y:v[i]) { if (p[x][y] != 1) return 0; } } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (p[i][j] == 1 && getpar(i) != getpar(j)) return 0; } } for (int i = 0; i < n; i++) { if (getpar(i) != i) continue; vector <int> cnt(n+2,0); for (auto x:v[i]) { for (int j = 0; j < n; j++) { if (p[x][j] == 2 && p[j][x] == 2) cnt[j]++; } } for (int j = 0; j < n; j++) { if (!(cnt[j] == 0 || cnt[j] == s[i])) return 0; } } vector <int> root; for (int i = 0; i < n; i++) { if (getpar(i) == i) root.push_back(i); } for (int i = 0; i < n; i++) { par[i] = i; s[i] = 1; v[i].clear(); } for (auto x:root) { for (auto y:root) { if (p[x][y] == 2) unionset(x,y); } } for (auto x:root) { v[getpar(x)].push_back(x); } for (auto x:root) { if (x != getpar(x)) continue; if (v[x].size() == 2) return 0; if (v[x].size() == 1) continue; for (auto a:v[x]) { for (auto b:v[x]) { if (a != b && p[a][b] != 2) return 0; } } for (int i = 0; i < v[x].size(); i++) { add(v[x][i],v[x][(i+1)%v[x].size()]); } } for (int i = 0; i < n; i++) answer[i][i] = 0; build(answer); return 1; }