#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
struct dsu {
vector<int> p;
int get(int v) {
return p[v] == v ? v : p[v] = get(p[v]);
}
bool uni(int v, int u) {
v = get(v), u = get(u);
p[v] = u;
return v != u;
}
dsu() {}
dsu(int n) {
p = vector<int>(n);
for (int i = 0; i < n; i++) p[i] = i;
}
};
int construct(vector<vector<int>> p) {
int n = p.size();
vector<vector<int>> g(n);
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;
g[i].push_back(j);
g[j].push_back(i);
}
}
vector<bool> vis(n, false);
vector<int> ind(n, -1);
vector<int> comp;
function<void(int, int)> dfs = [&](int v, int f) {
comp.push_back(v);
vis[v] = true;
ind[v] = f;
for (int u : g[v]) {
if (!vis[u]) {
dfs(u, f);
}
}
};
vector<pair<int, int>> ed;
for (int st = 0; st < n; st++) {
if (!vis[st]) {
comp = {};
dfs(st, st);
bool ok = true;
bool cycle = false;
for (int v : comp) {
for (int u : comp) {
ok &= p[v][u] != 0;
cycle |= p[v][u] == 2;
}
}
for (int v : comp) {
for (int i = 0; i < n; i++) {
if (ind[i] != st) ok &= p[v][i] == 0;
}
}
if (!ok) return 0;
int sz = comp.size();
dsu d(n);
for (int v : comp) {
for (int u : comp) {
if (p[v][u] == 1) d.uni(v, u);
}
}
for (int v : comp) {
for (int u : comp) {
int kek = 1 + (d.get(v) != d.get(u));
ok &= kek == p[v][u];
}
}
if (!ok) return 0;
if (cycle) {
vector<int> arr;
for (int v : comp) arr.push_back(d.get(v));
sort(arr.begin(), arr.end());
arr.erase(unique(arr.begin(), arr.end()), arr.end());
if (arr.size() < 3) return 0;
for (int i = 0; i < arr.size(); i++) ed.push_back({arr[i], arr[(i + 1) % arr.size()]});
vector<vector<int>> have(arr.size());
for (int v : comp) {
have[lower_bound(arr.begin(), arr.end(), d.get(v)) - arr.begin()].push_back(v);
}
for (int i = 0; i < arr.size(); i++) {
for (int j = 0; j + 1 < have[i].size(); j++) {
ed.push_back({have[i][j], have[i][j + 1]});
}
}
} else {
for (int i = 0; i + 1 < comp.size(); i++) ed.push_back({comp[i], comp[i + 1]});
}
}
}
for (auto e : ed) build(e.first, e.second);
return 1;
}
Compilation message
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:90:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for (int i = 0; i < arr.size(); i++) ed.push_back({arr[i], arr[(i + 1) % arr.size()]});
| ~~^~~~~~~~~~~~
supertrees.cpp:95:27: 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:33: 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 < have[i].size(); j++) {
| ~~~~~~^~~~~~~~~~~~~~~~
supertrees.cpp:102:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | for (int i = 0; i + 1 < comp.size(); i++) ed.push_back({comp[i], comp[i + 1]});
| ~~~~~~^~~~~~~~~~~~~
supertrees.cpp:70:11: warning: unused variable 'sz' [-Wunused-variable]
70 | int sz = comp.size();
| ^~
supertrees.cpp:106:29: error: could not convert 'e.std::pair<int, int>::first' from 'int' to 'std::vector<std::vector<int> >'
106 | for (auto e : ed) build(e.first, e.second);
| ~~^~~~~
| |
| int
