#include "supertrees.h"
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <cassert>
#include <iostream>
#include <optional>
using std::cout;
using std::endl;
using Matriz = std::vector<std::vector<int>>;
using Comp = std::unordered_set<int>;
using Rama = 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 ConstruyeCiclo(const std::vector<int>& vertices, Matriz& matriz) {
int n = vertices.size();
if (n < 3) {
return false;
}
for (int i = 0; i < n; ++i) {
int a = vertices[i];
int b = vertices[(i+1)%n];
matriz[a][b] = 1;
matriz[b][a] = 1;
}
return true;
}
bool Contiene(const Comp& c, int v) {
return c.count(v) > 0;
}
struct Componentes {
Componentes(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<Componentes> EncuentraComponentesConexas(const Matriz& caminos) {
int n = caminos.size();
Componentes 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;
}
std::optional<Componentes> EncuentraRamas(const Matriz& caminos, Comp& comp) {
int n = caminos.size();
Componentes ret(n);
for (int origen : comp) {
int comp_id = ret.comp_id[origen];
if (comp_id == -1) {
Comp rama;
for (int dest : comp) {
if (caminos[origen][dest] == 1) {
rama.insert(dest);
}
}
ret.AgregaComponente(std::move(rama));
} else {
auto& rama = ret.comps[comp_id];
for (int dest : comp) {
if ((caminos[origen][dest] == 1) != Contiene(rama, dest)){
return std::nullopt;
}
}
}
}
return ret;
}
bool Busca(const Matriz& matriz, int a) {
for (const auto& vec : matriz) {
for (int val : vec) {
if (val == a) {
return true;
}
}
}
return false;
}
int construct(std::vector<std::vector<int>> caminos) {
int n = caminos.size();
if (Busca(caminos, 3)) {
return 0;
}
auto conectividad = EncuentraComponentesConexas(caminos);
if (!conectividad) {
return 0;
}
Matriz answer(n, std::vector<int>(n, 0));
for (auto& c: conectividad->comps) {
auto ramas = EncuentraRamas(caminos, c);
if (!ramas) {
return 0;
}
std::vector<int> vertices_ciclo;
for (auto& rama : ramas->comps) {
assert(rama.size() > 0);
ConstruyeLista(rama, answer);
vertices_ciclo.push_back(*rama.begin());
}
if (vertices_ciclo.size() > 1 && !ConstruyeCiclo(vertices_ciclo, answer)) {
return 0;
}
}
build(answer);
return 1;
}
