#include "supertrees.h"
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <iostream>
#include <optional>
using std::cout;
using std::endl;
using Matriz = std::vector<std::vector<int>>;
using Comp = std::unordered_set<int>;
void ConstruyeLista(const Comp& comp, Matriz& matriz) {
int prev = -1;
for (int actual : comp) {
if (prev != -1) {
matriz[prev][actual] = 1;
matriz[actual][prev] = 1;
}
prev = actual;
}
}
bool Contiene(const Comp& c, int v) {
return c.count(v) > 0;
}
struct ComponentesConexas {
ComponentesConexas(int n) : n(n), comp_id(n, -1) {}
std::vector<Comp> comps;
int n;
std::vector<int> comp_id;
void AgregaComponente(Comp c) {
for (int v : c) {
comp_id[v] = comps.size();
}
comps.push_back(std::move(c));
}
};
std::optional<ComponentesConexas> EncuentraComponentesConexas(const Matriz& caminos) {
int n = caminos.size();
ComponentesConexas ret(n);
for (int origen = 0; origen < n; ++origen) {
int comp_id = ret.comp_id[origen];
if (comp_id == -1) {
Comp comp;
for (int dest = 0; dest < n; ++dest) {
if (caminos[origen][dest] > 0) {
comp.insert(dest);
}
}
ret.AgregaComponente(std::move(comp));
} else {
auto& comp = ret.comps[comp_id];
for (int dest = 0; dest < n; ++dest) {
if ((caminos[origen][dest] > 0) != Contiene(comp, dest)){
return std::nullopt;
}
}
}
}
return ret;
}
int construct(std::vector<std::vector<int>> caminos) {
int n = caminos.size();
auto comps = EncuentraComponentesConexas(caminos);
if (!comps) {
return 0;
}
Matriz answer(n, std::vector<int>(n, 0));
for (auto& c: comps->comps) {
ConstruyeLista(c, answer);
}
build(answer);
return 1;
}
