Language: C++

#include <bits/stdc++.h>
using namespace std;

template <typename T>
class Graph
{
public:
    struct Edge
    {
        long long to;
        T distance;
        Edge(const long long t, const T d)
        {
            this->to = t;
            this->distance = d;
        }
        bool operator<(const Edge &e) const
        {
            return this->distance < e.distance;
        }
        bool operator<=(const Edge &e) const
        {
            return this->distance <= e.distance;
        }
        bool operator>(const Edge &e) const
        {
            return this->distance > e.distance;
        }
        bool operator>=(const Edge &e) const
        {
            return this->distance >= e.distance;
        }
        bool operator==(const Edge &e) const
        {
            return this->distance == e.distance;
        }
    };
    class SimpleUnionFind
    {
    public:
        vector<long long> root;

        UnionFind(long long N)
        {
            this->root = vector<long long>(N + 1, -1);
        }

        long long find_root(long long A)
        {
            if (this->root[A] < 0)
            {
                return A;
            }
            else
            {
                this->root[A] = find_root(this->root[A]);
            }
            return this->root[A];
        }

        bool unite(long long A, long long B)
        {
            A = find_root(A);
            B = find_root(B);
            if (A == B)
            {
                return false;
            }

            if (size(A) < size(B))
            {
                swap(A, B);
            }

            this->root[A] += this->root[B];
            this->root[B] = A;

            return true;
        }

        bool has_same_root(long long A, long long B)
        {
            return find_root(A) == find_root(B);
        }
    };
    vector<vector<T>> adjacency_matrix;
    long long node;
    T initial_value;
    vector<vector<Edge>> edge;

    Graph(const long long N)
    {
        setNode(N);
        initializeEdgeVector();
    }

    Graph(const long long N, const T init)
    {
        setNode(N);
        initializeEdgeVector();
        setInitialValue(init);
    }

    void setNode(const long long N)
    {
        this->node = N + 1;
    }

    void setInitialValue(const long long init)
    {
        this->initial_value = init;
    }

    void initializeAdjacencyMatrix()
    {
        this->adjacency_matrix = vector<vector<T>>(
            this->node, vector<T>(this->node, this->initial_value));
    }

    void initializeAdjacencyMatrix(const T init)
    {
        setInitialValue(init);
        initializeAdjacencyMatrix();
    }

    void initializeEdgeVector()
    {
        this->edge = vector<vector<Edge>>(this->node);
    }

    void updateAdjacencyMatrix(const long long from, const long long to, const T distance = 1)
    {
        this->adjacency_matrix[from][to] = distance;
    }

    void addEdge(const long long from, const long long to, const T distance = 1)
    {
        this->edge[from].push_back({to, distance});
    }

    // O(V^3)
    // CAUTION: Use adjacency matrix
    vector<vector<T>> runFloydWarshall() const
    {
        vector<vector<T>> ret(this->adjacency_matrix);
        for (long long i = 0; i < this->node; i++)
        {
            for (long long j = 0; j < this->node; j++)
            {
                for (long long k = 0; k < this->node; k++)
                {
                    ret[j][k] = min(ret[j][k], ret[j][i] + ret[i][k]);
                }
            }
        }
        return ret;
    }

    // O(E)
    // CAUTION: Non-weighted only
    // CAUTION: Use edge vector
    T runBFS(const long long from, const long long to) const
    {
        vector<bool> visited(this->node, false);
        queue<long long> q;
        q.push(from);
        for (long long i = 1; i <= this->node && !q.empty(); i++)
        {
            queue<long long> tmp;
            while (!q.empty())
            {
                for (Edge e : this->edge[q.front()])
                {
                    if (e.to == to)
                    {
                        return i;
                    }
                    if (visited[e.to])
                    {
                        continue;
                    }
                    visited[e.to] = true;
                    tmp.push(e.to);
                }
                q.pop();
            }
            q = tmp;
        }
        return this->initial_value;
    }

    // O(VE)
    // CAUTION: Use edge vector
    vector<T> runBellmanFord(const long long from) const
    {
        vector<T> distance(this->node, this->initial_value);
        distance[from] = 0;

        for (long long i = 0; i < this->node - 1; i++)
        {
            for (long long j = 1; j < this->node; j++)
            {
                for (Edge e : this->edge[j])
                {
                    if (distance[e.to] > distance[j] + e.distance)
                    {
                        distance[e.to] = distance[j] + e.distance;
                    }
                }
            }
        }
        return distance;
    }

    // O(E + VlogV)
    // CAUTION: Use edge vector
    vector<T> runDijkstra(const long long from) const
    {
        vector<T> distance(this->node, this->initial_value);
        priority_queue<Edge, vector<Edge>, greater<Edge>> queue;
        queue.push(Edge(from, 0));
        while (!queue.empty())
        {
            T d = queue.top().distance;
            long long to = queue.top().to;
            queue.pop();
            if (distance[to] == this->initial_value)
            {
                distance[to] = d;
                for (Edge e : this->edge[to])
                {
                    if (distance[e.to] == this->initial_value)
                    {
                        queue.push({e.to, e.distance + d});
                    }
                }
            }
        }
        return distance;
    }

    // O(ElogV)
    // CAUTION: Use edge vector
    T runPrim() const
    {
        vector<bool> is_visited(this->node, false);
        T cost = 0;
        priority_queue<Edge, vector<Edge>, greater<Edge>> queue;
        queue.push(Edge(1, 0));
        while (!queue.empty())
        {
            T distance = queue.top().distance;
            long long to = queue.top().to;
            queue.pop();
            if (!is_visited[to])
            {
                cost += distance;
                is_visited[to] = true;
                for (Edge e : this->edge[to])
                {
                    queue.push({e.to, e.distance});
                }
            }
        }
        return cost;
    }

    T runKruskal() const
    {
        T cost = 0;
        vector<pair<Edge, int>> edge_from;
        for (int i = 0; i < this->node; i++)
        {
            for (auto e : this->edge[i];)
            {
                edge_from.push_back(make_pair(e, i)));
            }
        }
        sort(edge_from.begin(), edge_from.end());

        SimpleUnionFind uf(this->node);
        for (pair<Edge, int> e_f : edge_from)
        {
            auto e = e_f.first;
            int from = e_f.second;
            if (!uf.has_same_root(from, e.to))
            {
                unite(from, e.to);
                cost += e.distance;
            }
        }
        return cost;
    }
};

int main()
{
    int N;
    cin >> N;

    Graph<long long> g(N);

    vector<pair<long long, int>> X(N);
    vector<pair<long long, int>> Y(N);
    long long x, y;
    for (int i = 0; i < N; i++)
    {
        cin >> x >> y;
        X[i] = make_pair(x, i);
        Y[i] = make_pair(y, i);
    }

    sort(X.begin(), X.end());
    sort(Y.begin(), Y.end());
    for (int i = 1; i < N; i++)
    {
        g.addEdge(X[i - 1].second, X[i].second, X[i].first - X[i - 1].first);
        g.addEdge(X[i].second, X[i - 1].second, X[i].first - X[i - 1].first);

        g.addEdge(Y[i - 1].second, Y[i].second, Y[i].first - Y[i - 1].first);
        g.addEdge(Y[i].second, Y[i - 1].second, Y[i].first - Y[i - 1].first);
    }

    cout << g.runPrim() << endl;
}


Compiler output:
a.cc:43:9: error: ISO C++ forbids declaration of 'UnionFind' with no type [-fpermissive]
   43 |         UnionFind(long long N)
      |         ^~~~~~~~~
a.cc: In member function 'int Graph<T>::SimpleUnionFind::UnionFind(long long int)':
a.cc:46:9: warning: no return statement in function returning non-void [-Wreturn-type]
   46 |         }
      |         ^
a.cc: In member function 'bool Graph<T>::SimpleUnionFind::unite(long long int, long long int)':
a.cc:70:21: error: no matching function for call to 'size(long long int&)'
   70 |             if (size(A) < size(B))
      |                 ~~~~^~~
In file included from /usr/include/c++/14/string:53,
                 from /usr/include/c++/14/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:52,
                 from a.cc:1:
/usr/include/c++/14/bits/range_access.h:262:5: note: candidate: 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  262 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
/usr/include/c++/14/bits/range_access.h:262:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/range_access.h: In substitution of 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&) [with _Container = long long int]':
a.cc:70:21:   required from here
   70 |             if (size(A) < size(B))
      |                 ~~~~^~~
/usr/include/c++/14/bits/range_access.h:263:24: error: request for member 'size' in '__cont', which is of non-class type 'const long long int'
  263 |     -> decltype(__cont.size())
      |                 ~~~~~~~^~~~
/usr/include/c++/14/bits/range_access.h:272:5: note: candidate: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  272 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/14/bits/range_access.h:272:5: note:   template argument deduction/substitution failed:
a.cc:70:21: note:   mismatched types 'const _Tp [_Nm]' and 'long long int'
   70 |             if (size(A) < size(B))
      |                 ~~~~^~~
a.cc:70:31: error: no matching function for call to 'size(long long int&)'
   70 |             if (size(A) < size(B))
      |                           ~~~~^~~
/usr/include/c++/14/bits/range_access.h:262:5: note: candidate: 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  262 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
/usr/include/c++/14/bits/range_access.h:262:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/range_access.h: In substitution of 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&) [with _Container = long long int]':
a.cc:70:31:   required from here
   70 |             if (size(A) < size(B))
      |                           ~~~~^~~
/usr/include/c++/14/bits/range_access.h:263:24: error: request for member 'size' in '__cont', which is of non-class type 'const long long int'
  263 |     -> decltype(__cont.size())
      |                 ~~~~~~~^~~~
/usr/include/c++/14/bits/range_access.h:272:5: note: candidate: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  272 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/14/bits/range_access.h:272:5: note:   template argument deduction/substitution failed:
a.cc:70:31: note:   mismatched types 'const _Tp [_Nm]' and 'long long int'
   70 |             if (size(A) < size(B))
      |                           ~~~~^~~
a.cc: In member function 'T Graph<T>::runKruskal() const':
a.cc:274:40: error: expected ')' before ';' token
  274 |             for (auto e : this->edge[i];)
      |                                        ^
a.cc:274:17: note: to match this '('
  274 |             for (auto e : this->edge[i];)
      |                 ^
a.cc:274:41: error: expected primary-expression before ')' token
  274 |             for (auto e : this->edge[i];)
      |                                         ^