2. Kruskal MST (connecting points)

• https://en.wikipedia.org/wiki/Kruskal%27s_algorithm

Problem

Solutions

• C++

CPP

    #include <iostream>
    #include <sstream>
    #include <vector>
    #include <set>
    #include <unordered_set>
    #include <unordered_map>
    #include <cmath>
    #include <numeric>
    #include <iomanip>
    
    constexpr int INF = int( 1e3+1 );
    struct Vertex {
        int x{ 0 }, y{ 0 };
        Vertex() = default;
        Vertex( int x_, int y_ ) : x{ x_ }, y{ y_ } {}
        bool operator==( const Vertex& rhs ) const {
            return x == rhs.x && y == rhs.y;
        }
        size_t hash() const {
            return INF * x + y;
        }
    };
    struct Hash {
        size_t operator()( const Vertex& v ) const {
            return v.hash();
        }
    };
    struct Edge {
        Vertex u{ 0,0 }, v{ 0,0 };
        Edge( const Vertex& u_, const Vertex& v_ ) : u{ u_ }, v{ v_ } {}
        double length() const {
            auto X = abs( u.x - v.x ),
                 Y = abs( u.y - v.y );
            return sqrt( X*X + Y*Y );
        }
        bool operator<( const Edge& rhs ) const {
            return length() < rhs.length();
        }
    };
    using namespace std;
    using Vertices = unordered_set< Vertex, Hash >;
    using Edges = multiset< Edge >;
    using Parent = unordered_map< Vertex, Vertex, Hash >;
    
    Parent P;
    Vertex Find( const Vertex& x ){
        if( P[ x ] == x )
            return P[ x ];
        return P[ x ] = Find( P[ x ] );
    }
    bool Union( Vertex u, Vertex v ){
        u = Find( u );
        v = Find( v );
        if( u == v )
            return false;
        P[ u ] = v; // arbitrary choice
        return true;
    }
    
    int main() {
        auto N{ 0 }; cin >> N;
        Vertices V;
        for( auto[ x,y ]=Vertex{ 0,0 }; N-- && cin >> x >> y; ){
            Vertex v{ x,y };
            P[ v ] = v;
            V.insert( v );
        }
        Edges E;
        for( auto& u: V )
            for( auto& v: V )
                if( u == v )
                    continue;
                else
                    E.insert({ u,v });
        double ans{ 0 };
        for( auto& edge: E ){
            auto u = edge.u,
                 v = edge.v;
            if( Union( u,v ) )
                ans += edge.length();
        }
        cout << setprecision( 10 ) << ans << endl;
        return 0;
    }