// Grafo con listas de adyacencia. Los nodos son los enteros de 0 a node_count() - 1.
#ifndef GRAPH_H
#define GRAPH_H

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <tuple>
#include <vector>

// Una entrada de la lista de un nodo: a quién llega y cuánto pesa. Sin pesos, weight vale 1.
struct Edge {
    int to;
    int weight;
};

// Invariantes:
// - Todo destino de una lista es un nodo válido.
// - Las listas suman edge_count_ entradas si es dirigido, y 2 * edge_count_ si no lo es.
// - Si no es dirigido, cada entrada u -> v con peso w tiene su pareja v -> u con peso w, y no hay
//   lazos (aristas de un nodo a sí mismo).
//
// No revisa aristas repetidas: hacerlo costaría recorrer una lista en cada add_edge.
// std::vector es owner de toda la memoria, así que copiar, mover y destruir ya funcionan.
class Graph {
public:
    explicit Graph(int node_count, bool directed = false)
        : adjacency_(node_count), directed_(directed) {}

    void add_edge(int u, int v, int weight = 1) {
        assert(valid(u) && valid(v));
        assert(directed_ || u != v);
        adjacency_[u].push_back({v, weight});
        if (!directed_) {
            adjacency_[v].push_back({u, weight});
        }
        edge_count_++;
    }

    int node_count() const { return static_cast<int>(adjacency_.size()); }
    std::size_t edge_count() const { return edge_count_; }
    bool directed() const { return directed_; }

    // Referencia a la lista: recorrerla no copia nada. No agreguen aristas mientras la recorren.
    const std::vector<Edge>& neighbors(int u) const {
        assert(valid(u));
        return adjacency_[u];
    }

    // Recorre la lista de u: Θ(grado de u) en el peor caso.
    bool has_edge(int u, int v) const {
        for (const Edge& edge : neighbors(u)) {
            if (edge.to == v) {
                return true;
            }
        }
        return false;
    }

    bool check_invariants() const {
        using Arc = std::tuple<int, int, int>;
        std::vector<Arc> forward;
        std::vector<Arc> backward;
        for (int u = 0; u < node_count(); u++) {
            for (const Edge& edge : adjacency_[u]) {
                if (!valid(edge.to) || (!directed_ && edge.to == u)) {
                    return false;
                }
                forward.emplace_back(u, edge.to, edge.weight);
                backward.emplace_back(edge.to, u, edge.weight);
            }
        }
        if (forward.size() != (directed_ ? edge_count_ : 2 * edge_count_)) {
            return false;
        }
        if (directed_) {
            return true;
        }
        std::sort(forward.begin(), forward.end());
        std::sort(backward.begin(), backward.end());
        return forward == backward;
    }

private:
    friend struct GraphTestAccess;

    bool valid(int u) const { return 0 <= u && u < node_count(); }

    std::vector<std::vector<Edge>> adjacency_;
    std::size_t edge_count_ = 0;
    bool directed_;
};

#endif