#include "Graph.h"
#include "DSU.h"
#include <queue>
#include <functional>
#include <algorithm>
#include <limits>

Graph Graph::getSpaingTreePrima() const {
    Graph mst(n, false, true, 'L');
    auto g = toAdjList();

    const long long INF = std::numeric_limits<long long>::max();
    std::vector<long long> minEdge(n + 1, INF);
    std::vector<int> parent(n + 1, 0);
    std::vector<char> used(n + 1, 0);
    using Node = std::pair<long long, int>;
    std::priority_queue<Node, std::vector<Node>, std::greater<Node>> pq;

    for (int s = 1; s <= n; ++s) {
        if (used[s]) continue;
        minEdge[s] = 0;
        pq.push({0, s});
        while (!pq.empty()) {
            auto [w, u] = pq.top();
            pq.pop();
            if (used[u]) continue;
            used[u] = 1;
            if (parent[u] != 0) mst.addEdge(u, parent[u], (int)w);
            for (auto& e : g[u]) {
                int v = e.first, wgt = e.second;
                if (!used[v] && wgt < minEdge[v]) {
                    minEdge[v] = wgt;
                    parent[v] = u;
                    pq.push({wgt, v});
                }
            }
        }
    }
    return mst;
}

Graph Graph::getSpaingTreeKruscal() const {
    Graph mst(n, false, true, 'L');
    DSU dsu(n);

    auto el = toEdgeList();
    std::sort(el.begin(), el.end(), [](const auto& a, const auto& b) {
        return std::get<2>(a) < std::get<2>(b);
    });
    for (auto& e : el) {
        int a = std::get<0>(e), b = std::get<1>(e), w = std::get<2>(e);
        if (dsu.unite(a, b)) mst.addEdge(a, b, w);
    }
    return mst;
}

Graph Graph::getSpaingTreeBoruvka() const {
    Graph mst(n, false, true, 'L');
    DSU dsu(n);

    auto el = toEdgeList();
    int comp = n;
    while (comp > 1) {
        std::vector<int> best(n + 1, -1);
        for (int i = 0; i < (int)el.size(); ++i) {
            int ra = dsu.find(std::get<0>(el[i]));
            int rb = dsu.find(std::get<1>(el[i]));
            if (ra == rb) continue;
            int w = std::get<2>(el[i]);
            if (best[ra] == -1 || w < std::get<2>(el[best[ra]])) best[ra] = i;
            if (best[rb] == -1 || w < std::get<2>(el[best[rb]])) best[rb] = i;
        }
        bool merged = false;
        for (int v = 1; v <= n; ++v) {
            if (best[v] == -1) continue;
            auto& e = el[best[v]];
            if (dsu.unite(std::get<0>(e), std::get<1>(e))) {
                mst.addEdge(std::get<0>(e), std::get<1>(e), std::get<2>(e));
                --comp;
                merged = true;
            }
        }
        if (!merged) break;
    }
    return mst;
}