kruskal.cpp

#include "kruskal.h"
using namespace std;

// insertion sort based on (w,u,v)
static void sort_edges(vector<Edge> &arr)
{
    for (int i = 1; i < arr.size(); ++i)
    {
        Edge key = arr[i];
        int j = i - 1;
        while (j >= 0)
        {
            bool greater = false;
            if (arr[j].w > key.w)
                greater = true;
            else if (arr[j].w == key.w && arr[j].u > key.u)
                greater = true;
            else if (arr[j].w == key.w && arr[j].u == key.u && arr[j].v > key.v)
                greater = true;
            if (!greater)
                break;
            arr[j + 1] = arr[j];
            --j;
        }
        arr[j + 1] = key;
    }
}

pair<vector<Edge>, int> kruskal_mst(const Graph &G)
{
    vector<Edge> sorted = G.edges; // O(E) for copy
    sort_edges(sorted);            // O(E^2)

    //     std::sort(sorted.begin(), sorted.end(), [](const Edge &a, const Edge &b){  // O(ElogE)
    //     if (a.w != b.w) return a.w < b.w;
    //     if (a.u != b.u) return a.u < b.u;
    //     return a.v < b.v;
    // });

    UnionFind uf(G.n); // O(n)
    vector<Edge> mst;
    int total = 0;

    for (int i = 0; i < sorted.size(); ++i) // O(E. alpha(n))
    {
        Edge &e = sorted[i];
        if (!uf.same(e.u, e.v))
        {
            uf.unite(e.u, e.v);
            mst.push_back(e);
            total += e.w;
            if ((int)mst.size() == G.n - 1)
                break;
        }
    }
    return {mst, total};
}

// O(E^2) + O(E. alpha(n)) + O(n) = O(E^2)