// Grafo no dirigido con matriz de adyacencia: un byte por cada par de nodos.
#ifndef MATRIX_GRAPH_H
#define MATRIX_GRAPH_H

#include <cassert>
#include <cstddef>
#include <vector>

// Invariantes: la tabla tiene n * n celdas, es simétrica y su diagonal vale 0.
class MatrixGraph {
public:
    explicit MatrixGraph(int node_count)
        : n_(node_count), cells_(static_cast<std::size_t>(node_count) * node_count, 0) {}

    void add_edge(int u, int v) {
        assert(u != v);
        cell(u, v) = 1;
        cell(v, u) = 1;
    }

    // Una sola lectura, sin importar cuántas aristas haya.
    bool has_edge(int u, int v) const { return cells_[index(u, v)] != 0; }
    int node_count() const { return n_; }
    std::size_t bytes() const { return sizeof(MatrixGraph) + cells_.capacity(); }

    bool check_invariants() const {
        if (cells_.size() != static_cast<std::size_t>(n_) * n_) {
            return false;
        }
        for (int u = 0; u < n_; u++) {
            if (has_edge(u, u)) {
                return false;
            }
            for (int v = 0; v < u; v++) {
                if (has_edge(u, v) != has_edge(v, u)) {
                    return false;
                }
            }
        }
        return true;
    }

private:
    std::size_t index(int u, int v) const {
        assert(0 <= u && u < n_ && 0 <= v && v < n_);
        return static_cast<std::size_t>(u) * n_ + v;
    }
    char& cell(int u, int v) { return cells_[index(u, v)]; }

    int n_;
    std::vector<char> cells_;
};

#endif