// Grafos pequeños y las fuerzas brutas de la semana. Un conjunto de nodos es una máscara de bits.
#ifndef GRAPHS_H
#define GRAPHS_H

#include <bit>
#include <queue>
#include <string>
#include <utility>
#include <vector>

// Grafo no dirigido y simple: sin lazos y sin aristas repetidas.
struct Graph {
    int n = 0;
    std::vector<std::pair<int, int>> edges;

    bool adjacent(int u, int v) const {
        for (auto [a, b] : edges) {
            if ((a == u && b == v) || (a == v && b == u)) return true;
        }
        return false;
    }
};

// Una instancia de un problema de decisión sobre grafos: ¿hay un conjunto de tamaño k?
struct Instance {
    Graph graph;
    int k = 0;
};

inline bool contains(unsigned set, int v) { return ((set >> v) & 1u) != 0; }

// Verificadores: reciben el certificado, y solo miran cada arista una vez. Cuestan O(V + E).
inline bool is_independent_set(const Graph& g, unsigned set) {
    for (auto [u, v] : g.edges) {
        if (contains(set, u) && contains(set, v)) return false;
    }
    return true;
}

inline bool is_vertex_cover(const Graph& g, unsigned set) {
    for (auto [u, v] : g.edges) {
        if (!contains(set, u) && !contains(set, v)) return false;
    }
    return true;
}

// Mira cada par de nodos: O(V² · E) con esta representación tan simple, y O(V²) con una matriz.
inline bool is_clique(const Graph& g, unsigned set) {
    for (int u = 0; u < g.n; u++) {
        for (int v = u + 1; v < g.n; v++) {
            if (contains(set, u) && contains(set, v) && !g.adjacent(u, v)) return false;
        }
    }
    return true;
}

inline bool is_proper_coloring(const Graph& g, const std::vector<int>& color) {
    for (auto [u, v] : g.edges) {
        if (color[u] == color[v]) return false;
    }
    return true;
}

// Fuerza bruta: las 2ⁿ máscaras.
template <typename Check, typename Size>
bool any_set(const Graph& g, Check check, Size size_ok) {
    const unsigned total = 1u << g.n;
    for (unsigned set = 0; set < total; set++) {
        if (size_ok(std::popcount(set)) && check(g, set)) return true;
    }
    return false;
}

// ¿Hay un conjunto independiente de tamaño al menos k?
inline bool has_independent_set(const Instance& in) {
    return any_set(in.graph, is_independent_set, [&](int size) { return size >= in.k; });
}

// ¿Hay una cobertura de vértices de tamaño a lo sumo k?
inline bool has_vertex_cover(const Instance& in) {
    return any_set(in.graph, is_vertex_cover, [&](int size) { return size <= in.k; });
}

// ¿Hay un clique de tamaño al menos k?
inline bool has_clique(const Instance& in) {
    return any_set(in.graph, is_clique, [&](int size) { return size >= in.k; });
}

inline Graph complement(const Graph& g) {
    Graph h{g.n, {}};
    for (int u = 0; u < g.n; u++) {
        for (int v = u + 1; v < g.n; v++) {
            if (!g.adjacent(u, v)) h.edges.emplace_back(u, v);
        }
    }
    return h;
}

// Las reducciones de los apuntes. Ninguna mira si la respuesta es sí o no.
inline Instance independent_set_to_vertex_cover(const Instance& in) { return {in.graph, in.graph.n - in.k}; }
inline Instance independent_set_to_clique(const Instance& in) { return {complement(in.graph), in.k}; }
inline Instance vertex_cover_to_clique(const Instance& in) {
    return independent_set_to_clique(independent_set_to_vertex_cover(in));
}

// El grafo con un nodo nuevo, vecino de todos.
inline Graph add_apex(const Graph& g) {
    Graph h = g;
    for (int v = 0; v < g.n; v++) h.edges.emplace_back(v, g.n);
    h.n = g.n + 1;
    return h;
}

// 2-coloreo con BFS, en O(V + E) con listas de adyacencia: cada componente se pinta por capas.
inline bool two_colorable(const Graph& g) {
    std::vector<std::vector<int>> next(g.n);
    for (auto [u, v] : g.edges) {
        next[u].push_back(v);
        next[v].push_back(u);
    }
    std::vector<int> color(g.n, -1);
    for (int start = 0; start < g.n; start++) {
        if (color[start] != -1) continue;
        color[start] = 0;
        std::queue<int> pending;
        pending.push(start);
        while (!pending.empty()) {
            int u = pending.front();
            pending.pop();
            for (int v : next[u]) {
                if (color[v] == -1) {
                    color[v] = 1 - color[u];
                    pending.push(v);
                } else if (color[v] == color[u]) {
                    return false;
                }
            }
        }
    }
    return true;
}

// Fuerza bruta: prueba las colorsⁿ formas de pintar.
inline bool colorable_brute_force(const Graph& g, int colors) {
    std::vector<int> color(g.n, 0);
    while (true) {
        if (is_proper_coloring(g, color)) return true;
        int v = 0;
        while (v < g.n && ++color[v] == colors) color[v++] = 0;
        if (v == g.n) return false;
    }
}

inline std::string set_to_string(unsigned set, int n) {
    std::string text = "{";
    for (int v = 0; v < n; v++) {
        if (contains(set, v)) text += (text.size() > 1 ? ", " : "") + std::to_string(v);
    }
    return text + "}";
}

#endif