// El grafo de la clase: Kruskal y Prim paso a paso, y las ideas parecidas que fallan.
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>

#include "mst.h"

namespace {

const int kNodes = 7;

std::vector<Edge> class_graph() {
    return {{0, 1, 7}, {0, 3, 5}, {1, 2, 8}, {1, 3, 9}, {1, 4, 6}, {2, 4, 4},
            {3, 4, 15}, {3, 5, 10}, {4, 5, 12}, {4, 6, 11}, {5, 6, 13}};
}

std::string edges_text(const std::vector<Edge>& edges) {
    std::string text;
    for (const Edge& e : edges) {
        text += std::to_string(e.u) + "-" + std::to_string(e.v) + ":" + std::to_string(e.weight) + " ";
    }
    if (!text.empty()) text.pop_back();
    return text;
}

void kruskal_trace(const std::vector<Edge>& edges) {
    std::cout << "Kruskal:\n";
    std::cout << "  arista  peso  se toma  grupos después\n";
    UnionFind sets(kNodes);
    std::vector<Edge> so_far;
    for (const Edge& e : sorted_by_weight(edges)) {
        bool taken = sets.unite(e.u, e.v);
        if (taken) so_far.push_back(e);
        std::printf("  %d-%d %7d  %s      %d\n", e.u, e.v, e.weight, taken ? "sí" : "no", sets.sets());
    }
    std::cout << "  costo " << total_weight(so_far) << ", " << so_far.size() << " aristas\n";
}

void prim_trace(const std::vector<Edge>& edges) {
    std::cout << "\nPrim desde 0 (arista que sale de la cola, y qué pasa):\n";
    using Entry = std::tuple<int, int, int>;
    auto adj = adjacency(kNodes, edges);
    std::vector<bool> in_tree(kNodes, false);
    std::priority_queue<Entry, std::vector<Entry>, std::greater<Entry>> heap;
    long long pushes = 0;
    long long stale = 0;
    long long cost = 0;
    auto add_node = [&](int u) {
        in_tree[u] = true;
        for (const Neighbor& nb : adj[u]) {
            if (!in_tree[nb.to]) {
                heap.push({nb.weight, nb.to, u});
                pushes++;
            }
        }
    };
    add_node(0);
    while (!heap.empty()) {
        auto [weight, v, from] = heap.top();
        heap.pop();
        if (in_tree[v]) {
            stale++;
            std::printf("  %d-%d:%-3d descartada: %d ya está en el árbol\n", from, v, weight, v);
            continue;
        }
        add_node(v);
        cost += weight;
        std::printf("  %d-%d:%-3d entra %d, quedan %zu en la cola\n", from, v, weight, v, heap.size());
    }
    std::cout << "  costo " << cost << ", entradas " << pushes << ", descartadas " << stale << ", aristas del grafo "
              << edges.size() << "\n";
}

void show_idea(const std::string& name, const std::vector<Edge>& chosen) {
    std::cout << name << "\n";
    std::cout << "  aristas: " << edges_text(chosen) << "\n";
    std::cout << "  costo " << total_weight(chosen) << ", grupos " << count_components(kNodes, chosen) << ", "
              << (is_spanning_tree(kNodes, chosen) ? "es árbol de expansión" : "no es árbol de expansión") << "\n";
}

}  // namespace

int main() {
    std::vector<Edge> edges = class_graph();
    kruskal_trace(edges);
    prim_trace(edges);

    auto spanning = all_spanning_trees(kNodes, edges);
    auto minimum = all_minimum_trees(kNodes, edges);
    long long best = 0;
    for (int c : minimum[0]) best += edges[c].weight;
    std::cout << "\nFuerza bruta: " << spanning.size() << " árboles de expansión, mínimo " << best << ", "
              << minimum.size() << " de ese costo\n\n";

    show_idea("Las n - 1 aristas más baratas:", cheapest_edges_only(kNodes, edges));
    show_idea("Cada nodo elige su arista más barata:", cheapest_per_node(kNodes, edges));
    show_idea("Árbol de caminos mínimos desde 0:", dijkstra(kNodes, edges, 0).tree);
}