#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1007;
vector<int> g[N];
bool vis[N];
int cmp[N];
vector<int> comp;
int par[N];
int find_par(int v) {
return par[v] == v ? v : par[v] = find_par(par[v]);
}
bool unite(int v, int u) {
v = find_par(v);
u = find_par(u);
par[v] = u;
return v != u;
}
void dfs(int v, int st) {
vis[v] = true;
cmp[v] = st;
comp.push_back(v);
for (int u : g[v]) {
if (!vis[u]) dfs(u, st);
}
}
int construct(vector<vector<int>> p) {
int n = p.size();
for (int i = 0; i < n; i++) g[i].clear();
for (int i = 0; i < n; i++) {
if (p[i][i] != 1) return 0;
for (int j = 0; j < i; j++) {
if (p[i][j] != p[j][i]) return 0;
if (p[i][j] == 3) return 0;
if (p[i][j] > 0) {
g[i].push_back(j);
g[j].push_back(i);
}
}
}
vector<vector<int>> b(n, vector<int>(n, 0));
auto add_edge = [&](int v, int u) {
b[v][u] = b[u][v] = 1;
};
for (int i = 0; i < n; i++) {
vis[i] = false;
col[i] = -1;
}
for (int st = 0; st < n; st++) {
if (!vis[st]) {
comp = {};
dfs(st, st);
bool ok = true;
for (int v : comp) {
for (int u : comp) ok &= p[v][u] > 0;
for (int i = 0; i < n; i++) {
if (cmp[i] != st) ok &= p[v][i] == 0;
}
}
if (!ok) return 0;
bool has = false;
for (int v : comp) {
for (int u : comp) has |= p[v][u] == 2;
}
if (has) {
for (int i = 0; i < n; i++) par[i] = i;
for (int v : comp) {
for (int u : comp) {
if (p[v][u] == 1) unite(v, u);
}
}
for (int v : comp) {
for (int u : comp) {
if (find_par(v) == find_par(u) && p[v][u] == 2) return 0;
if (find_par(v) != find_par(u) && p[v][u] == 1) return 0;
}
}
for (int v : comp) find_par(v);
vector<int> arr;
for (int v : comp) arr.push_back(find_par(v));
sort(arr.begin(), arr.end());
arr.erase(unique(arr.begin(), arr.end()), arr.end());
if (arr.size() < 3) return 0;
vector<vector<int>> arrs(arr.size());
for (int v : comp) {
arrs[lower_bound(arr.begin(), arr.end(), find_par(v)) - arr.begin()].push_back(v);
}
for (int i = 0; i < arr.size(); i++) {
for (int j = 0; j + 1 < arrs[i].size(); j++) add_edge(arrs[i][j], arrs[i][j + 1]);
}
for (int i = 0; i < arr.size(); i++) add_edge(arr[i], arr[(i + 1) % (int)arr.size()]);
} else {
for (int i = 0; i + 1 < comp.size(); i++) add_edge(comp[i], comp[i + 1]);
}
}
}
build(b);
return 1;
}
Compilation message
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:54:9: error: 'col' was not declared in this scope; did you mean 'cosl'?
54 | col[i] = -1;
| ^~~
| cosl
supertrees.cpp:95:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for (int i = 0; i < arr.size(); i++) {
| ~~^~~~~~~~~~~~
supertrees.cpp:96:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for (int j = 0; j + 1 < arrs[i].size(); j++) add_edge(arrs[i][j], arrs[i][j + 1]);
| ~~~~~~^~~~~~~~~~~~~~~~
supertrees.cpp:98:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for (int i = 0; i < arr.size(); i++) add_edge(arr[i], arr[(i + 1) % (int)arr.size()]);
| ~~^~~~~~~~~~~~
supertrees.cpp:100:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | for (int i = 0; i + 1 < comp.size(); i++) add_edge(comp[i], comp[i + 1]);
| ~~~~~~^~~~~~~~~~~~~
