#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
class DisjointSets {
private:
int n;
vector<int> parents;
vector<int> sizes;
public:
DisjointSets(int size) : parents(size), sizes(size, 1) {
for (int i = 0; i < size; i++) { parents[i] = i; }
n = size;
}
int find(int x) { return parents[x] == x ? x : (parents[x] = find(parents[x])); }
bool unite(int x, int y) {
int x_root = find(x);
int y_root = find(y);
if (x_root == y_root) { return false; }
if (sizes[x_root] < sizes[y_root]) { swap(x_root, y_root); }
sizes[x_root] += sizes[y_root];
parents[y_root] = x_root;
return true;
}
bool connected(int x, int y) { return find(x) == find(y); }
vector<vector<int>> comps() {
map<int, vector<int>> mp;
for (int i = 0; i < n; i++) mp[find(i)].push_back(i);
vector<vector<int>> fin; for (auto &x : mp) fin.push_back(x.second);
return fin;
}
};
vector<vector<int>> answer;
void ans(int i, int j) {
if (i == j) return;
answer[i][j] = answer[j][i] = 1;
}
int construct(vector<vector<int>> p) {
int n = p.size(); answer.assign(n, vector<int>(n));
DisjointSets connectivity(n);
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] > 0) connectivity.unite(i, j);
}
}
vector<vector<int>> cs = connectivity.comps();
for (auto &comp : cs) {
int m = (int)comp.size();
vector<int> incomp(n);
for (int i = 0; i < m; i++) {
for (int j = i+1; j < m; j++) {
if (p[comp[i]][comp[j]] == 0) {
// cout << "connectivity fail\n";
return 0;
}
}
}
// cout << "curcomp\n";
DisjointSets trees(n);
for (auto &n1 : comp) {
incomp[n1] = 1;
// cout << n1 << " in comp\n";
for (auto &n2 : comp) {
if (n1 == n2) continue;
if (p[n1][n2] == 1) trees.unite(n1, n2);
}
}
// cout << "treecomps\n";
for (auto &treecomp : trees.comps()) {
for (auto &n1 : treecomp) {
// cout << n1 << " ";
for (auto &n2 : treecomp) {
if (n1 == n2) continue;
if (p[n1][n2] == 2) {
// cout << "tree fail\n";
return 0;
}
}
}
// cout << '\n';
}
map<int, vector<int>> mp2;
for (int i = 0; i < n; i++) {
if (!incomp[i]) continue;
mp2[trees.find(i)].push_back(i);
}
if ((int)mp2.size() == 2) {
// cout << "two trees\n";
return 0;
}
vector<int> represent;
for (auto &treecomp : trees.comps()) {
if (!incomp[treecomp[0]]) continue;
int m = (int)treecomp.size();
for (int i = 0; i < m-1; i++) ans(treecomp[i], treecomp[i + 1]);
represent.push_back(treecomp[0]);
}
for (int i = 0; i < (int)represent.size(); i++) ans(represent[i], represent[(i + 1) % (int)(represent.size())]);
}
build(answer);
return 1;
}
