// Cobertura de vértices: un método con factor 2 demostrado, dos reglas parecidas y un árbitro.
// Un grafo es una cantidad de nodos y una lista de aristas.
#pragma once
#include <cstddef>
#include <utility>
#include <vector>

namespace cover {

using Edge = std::pair<int, int>;
using Edges = std::vector<Edge>;
using Nodes = std::vector<int>;

inline std::size_t at(int i) { return static_cast<std::size_t>(i); }

inline bool is_cover(const Nodes& chosen, int n, const Edges& edges) {
    std::vector<char> in(at(n), 0);
    for (int v : chosen) in[at(v)] = 1;
    for (const auto& [u, v] : edges) {
        if (in[at(u)] == 0 && in[at(v)] == 0) return false;
    }
    return true;
}

struct Matched {
    Edges matching;
    Nodes cover;
};

// Revisa las aristas en orden. Si ninguna punta de la arista está elegida, entra al matching y se
// eligen las dos. Invariante: lo elegido son las puntas del matching, y las aristas ya revisadas
// tienen alguna punta elegida. Al final el matching es maximal: no le cabe ninguna arista más.
inline Matched matching_cover(int n, const Edges& edges) {
    std::vector<char> used(at(n), 0);
    Matched result;
    for (const auto& [u, v] : edges) {
        if (used[at(u)] == 0 && used[at(v)] == 0) {
            used[at(u)] = used[at(v)] = 1;
            result.matching.push_back({u, v});
            result.cover.push_back(u);
            result.cover.push_back(v);
        }
    }
    return result;
}

// Una idea parecida que falla: por cada arista sin cubrir, elegir solo una punta, la segunda.
inline Nodes one_endpoint_cover(int n, const Edges& edges) {
    std::vector<char> used(at(n), 0);
    Nodes chosen;
    for (const auto& [u, v] : edges) {
        if (used[at(u)] == 0 && used[at(v)] == 0) {
            used[at(v)] = 1;
            chosen.push_back(v);
        }
    }
    return chosen;
}

// La regla natural: repetir con el nodo que cubre más aristas sin cubrir. En un empate, el de menor número.
inline Nodes greedy_degree_cover(int n, const Edges& edges) {
    std::vector<char> alive(edges.size(), 1);
    Nodes chosen;
    while (true) {
        std::vector<int> degree(at(n), 0);
        for (std::size_t e = 0; e < edges.size(); e++) {
            if (alive[e] != 0) {
                degree[at(edges[e].first)]++;
                degree[at(edges[e].second)]++;
            }
        }
        int best = 0;
        for (int v = 1; v < n; v++) {
            if (degree[at(v)] > degree[at(best)]) best = v;
        }
        if (n == 0 || degree[at(best)] == 0) return chosen;
        chosen.push_back(best);
        for (std::size_t e = 0; e < edges.size(); e++) {
            if (edges[e].first == best || edges[e].second == best) alive[e] = 0;
        }
    }
}

// El árbitro: prueba los 2ⁿ subconjuntos. Solo sirve para grafos chicos.
inline int minimum_cover_size(int n, const Edges& edges) {
    int best = n;
    for (unsigned mask = 0; mask < (1U << n); mask++) {
        bool covers = true;
        for (const auto& [u, v] : edges) {
            if (((mask >> u) & 1U) == 0 && ((mask >> v) & 1U) == 0) {
                covers = false;
                break;
            }
        }
        if (covers) {
            int size = 0;
            for (int v = 0; v < n; v++) size += static_cast<int>((mask >> v) & 1U);
            if (size < best) best = size;
        }
    }
    return best;
}

// Una trampa para la regla del mayor grado. Hay k nodos a la izquierda, 0, ..., k - 1. Para cada i de
// 2 a k hay ⌊k/i⌋ nodos a la derecha, y cada uno se une a i nodos de la izquierda, sin repetirlos
// dentro del grupo. Los k nodos de la izquierda ya son una cobertura, así que el óptimo es a lo sumo k.
struct Trap {
    int nodes;
    Edges edges;
    int right_nodes;
};

inline Trap greedy_trap(int k) {
    Trap trap{k, {}, 0};
    for (int i = 2; i <= k; i++) {
        for (int group = 0; group < k / i; group++) {
            const int r = trap.nodes++;
            trap.right_nodes++;
            for (int offset = 0; offset < i; offset++) trap.edges.push_back({group * i + offset, r});
        }
    }
    return trap;
}

}  // namespace cover