#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector <ll> P, H;
vector <vector <int>> sol;
ll dsu_find(ll x){
if (P[x] == x)return x;
return (P[x] = dsu_find(P[x]));
}
void dsu_union(ll x, ll y){
x = dsu_find(x), y = dsu_find(y);
if (x == y)return;
if (H[x] > H[y])P[y] = x;
if (H[x] < H[y])P[x] = y;
if (H[x] == H[y]){
P[y] = x;
H[x]++;
}
}
bool cmp(ll a, ll b){
return (P[a] < P[b]);
}
bool solve(vector <ll> &v, vector <vector <int>> &p){
ll n = v.size();
for (int i = 0; i < n; i++){
for (int j = i+1; j < n; j++)if (p[v[i]][v[j]] == 1)dsu_union(v[i], v[j]);
}
for (int i = 0; i < n; i++)P[v[i]] = dsu_find(v[i]);
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++)if (p[v[i]][v[j]] == 2 && P[v[i]] == P[v[j]])return 0;
}
sort(v.begin(), v.end(), cmp);
ll current = 0;
for (int i = 1; i < n; i++){
if (P[v[i]] == P[v[i-1]]){
sol[v[i]][v[i-1]] = 1;
sol[v[i-1]][v[i]] = 1;
}
else {
sol[v[i]][v[current]] = 1;
sol[v[current]][v[i]] = 1;
current = i;
}
}
sol[v[current]][v[0]] = 1;
sol[v[0]][v[current]] = 1;
return 1;
}
/*void build(vector <vector <int>> b){
/*for (int i = 0; i < b.size(); i++){
cerr << endl;
for (int j = 0; j < b.size(); j++){
cerr << b[i][j] << " ";
}
}
return;
}
*/
int construct(vector <vector <int>> p){
ll n = p.size();
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++)if (p[i][j] == 3)return 0;
}
P.resize(n);
H.resize(n, 0);
for (int i = 0; i < n; i++)P[i] = i;
for (int i = 0; i < n; i++){
for (int j = i+1; j < n; j++)if (p[i][j] > 0)dsu_union(i, j);
}
for (int i = 0; i < n; i++)P[i] = dsu_find(i);
for (int i = 0; i < n; i++){
for (int j = i+1; j < n; j++)if (p[i][j] == 0 && P[i] == P[j])return 0;
}
vector <pair<ll, ll>> t(n);
for (int i = 0; i < n; i++)t[i] = {P[i], i};
sort(t.begin(), t.end());
sol.resize(n, vector <int> (n, 0));
for (int i = 0; i < n; i++){
P[i] = i;
H[i] = 0;
}
vector <ll> v;
for (int i = 0; i < n; i++){
if (i > 0 && t[i].first != t[i-1].first){
if (!solve(v, p))return 0;
v.clear();
}
v.push_back(t[i].second);
}
if (!solve(v, p))return 0;
for (int i = 0; i < n; i++)sol[i][i] = 0;
build(sol);
return 1;
}
/*int main(){
int n; cin >> n;
vector <vector <int>> p(n, vector <int> (n));
for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)cin >> p[i][j];
cout << construct(p);
}*/
/*
4
1 1 2 2
1 1 2 2
2 2 1 2
2 2 2 1
*/
Compilation message
supertrees.cpp:58:5: warning: "/*" within comment [-Wcomment]
58 | /*for (int i = 0; i < b.size(); i++){
|
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:101:5: error: 'build' was not declared in this scope
101 | build(sol);
| ^~~~~
