#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++) { 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> fix(n,0); for (int i = 0; i < n; i++) { if (getpar(i) != i || fix[getpar(i)]) continue; vector <int> res(1,i); fix[i] = 1; vector <int> cur(n,0); cur[i] = 1; for (int j = 0; j < n; j++) { if (p[i][j] == 2 && fix[getpar(j)] == 0) res.push_back(getpar(j)),fix[getpar(j)] = 1,cur[getpar(i)] = 1; } res.push_back(i); for (int j = 0; j < (res).size()-1; j++) { add(res[j],res[j+1]); } if (res.size() == 3) return 0; // for (auto x:res) { // for (auto y:res) { // if (x == y) continue; // if (p[x][y] != 2) return 0; // } // } // for (auto x:res) { // for (int j = 0; j < n; j++) { // if (getpar(j) == x) continue; // if (p[x][j] == 2 && cur[getpar(j)] == 0) return 0; // } // } } for (int i = 0; i < n; i++) answer[i][i] = 0; build(answer); return 1; }