Basic MST Problem, problem link: https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=975

UVA10034.cpp

#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
#include <map>
#include <iomanip>
using namespace std;
#define pdd pair <double, double>

struct edge{
    int p1, p2;
    double cost;
    bool operator <(const edge& a) const{
        return cost < a.cost;
    }
};

double distance(pdd a, pdd b)
{
    return sqrt(pow(a.first - b.first, 2) + pow(a.second - b.second, 2));
}

int link[400], size[400];

void init(int n)
{
    for(int i = 0; i <= n; i++) link[i] = i, size[i] = 1;
}

int find(int x)
{
    while(x != link[x]) x = link[x];
    return x;
}

void unite(int p1, int p2)
{
    if(size[p1] < size[p2]) swap(p1, p2);
    size[p1] += size[p2];
    link[p2] = p1;
}

double kruskal(vector < edge > edges, int node)
{
    sort(edges.begin(), edges.end());
    init(node);
    double ans = 0.0;
    int t1, t2, takenEdge = 0;
    for(edge e: edges){
        t1 = find(e.p1), t2 = find(e.p2);
        if(t1 == t2) continue;
        unite(t1, t2), ans += e.cost, takenEdge++;
        if(takenEdge == node - 1) return ans;
    }

}

int main()
{
    int t;
    cin >> t;
    bool check = false;
    while(t--){
        if(check) cout << '\n';
        int n, no = 0;
        vector < pdd > points;
        vector < edge > edges;
        edge tempNode;
        cin >> n;
        double x, y;
        for(int i = 0; i < n; i++)
        {
            cin >> x >> y;
            points.push_back( {x, y} );
        }   
        
        map < pdd, int> m;
        for(int i = 0; i < n - 1; i++)
            for(int j = i + 1; j < n; j++){
                if(!m[points[i]]) m[points[i]] = ++no;
                if(!m[points[j]]) m[points[j]] = ++no;
                tempNode.p1 = m[points[i]];
                tempNode.p2 = m[points[j]];
                tempNode.cost = distance(points[i], points[j]);
                edges.push_back(tempNode);
            }
        cout << setprecision(2) << fixed;
        cout << kruskal(edges, n) << '\n';
        check = true;
    }

    return 0;
}