Language: C++

#include <bits/stdc++.h>

#define TYPE(c)   remove_reference_t<decltype(c)>
#define REP(i, n) for(TYPE(n) i = 0; i < n; i++)
#define FOR(v, c) for(TYPE(c.begin()) v = c.begin(); v != c.end(); v++)
#define ALL(c)    c.begin(), c.end()
#define SORT(c)   sort(ALL(c))
#define RSORT(c)  sort(ALL(c), greater<TYPE(c)::value_type>())
#define UNIQUE(c) c.erase(unique(ALL(c)), c.end())

using namespace std;
using ll = long long;

constexpr int MOD  = (int)1e9 + 7;
constexpr int INF  = (int)1e9 + 1;
constexpr ll  LINF = (ll)1e18 + 1;
template<typename S, typename T> ostream& operator<<(ostream &os, const pair<S, T>& p)
{ return os << "(" << p.first << "," << p.second << ")"; }
template<typename T> auto operator<<(ostream& os, const T& t)
    -> typename conditional<true, ostream&, decltype(*t.begin())>::type
{ os << "["; FOR(v, t) { if(v != t.begin()) os << ","; os << *v; } os << "]"; return os; }

class Graph {
    using ll = long long;
public:
    enum class Type { Directed, Undirected };
    struct Edge {
        ll   cost;
        bool validity;
        Edge(const ll& _cost = 1) :
            cost(_cost), validity(true) { }
        friend std::ostream& operator <<(std::ostream& os, const std::shared_ptr<Edge>& e) {
            os << "cost : " << e->cost << ", " << "validity : " << e->validity;
            return os;
        }
    };
    struct Vertex {
        ll cost;
        Vertex(const ll& _cost = (ll)1e9 + 1) : cost(_cost) { }
        friend std::ostream& operator <<(std::ostream& os, const Vertex& v) {
            os << "cost : " << v.cost;
            return os;
        }
    };
    const Type edge_type;
    std::vector<Vertex> vertices;
    std::vector<std::map<ll, std::shared_ptr<Edge>>> edges;
    Graph(const ll& nof_vertex, const Type& edge_type, const ll& vertices_initial_cost = (ll)1e9 + 1) :
        edge_type(edge_type), vertices(nof_vertex, Vertex(vertices_initial_cost)), edges(nof_vertex) { }
    void setCostToAllVertices(const ll& val) {
        std::fill(vertices.begin(), vertices.end(), Vertex(val));
    };
    void addEdge(const ll& src, const ll& dst, const ll& cost = 1) {
        auto edge = std::make_shared<Edge>(src, dst, cost);
        edges[src].emplace(dst, edge);
        if(edge_type == Type::Undirected) edges[dst].emplace(src, edge);
    }
    friend std::ostream& operator <<(std::ostream& os, const Graph& g) {
        os << std::endl
           << "--- Vertex Information ---" << std::endl;
        for(size_t i = 0; i < g.vertices.size(); i++)
            os << "[[" << i << "] " << g.vertices[i] << "]" << std::endl;
        os << "---- Edge Information ----" << std::endl;
        for(size_t i = 0; i < g.vertices.size(); i++)
            for(const auto& e : g.edges[i])
                os << "[" << i << " -> " << e.first  << "] " << "[" << e.second << "]" << std::endl;
        os << "--------------------------";
        return os;
    }
};

class UnionFind {
    using ll = long long;
public:
    struct Node {
        ll parent, weight, size, rank;
        Node(const ll& _parent = 0,
             const ll& _weight = 0,
             const ll& _size   = 1,
             const ll& _rank   = 0) :
            parent(_parent),
            weight(_weight),
            size(_size),
            rank(_rank) { }
    };

    explicit UnionFind(const ll& num_node) {
        node_.reserve(num_node);
        for(ll i = 0; i < num_node; i++) {
            node_.emplace_back(i);
        }
    }

    const std::vector<Node>& getNode() const {
        return node_;
    }

    ll searchAndZipRoot(const ll& x) {
        if(node_[x].parent == x) {
            return x;
        }
        else {
            node_[x].weight += node_[node_[x].parent].weight;
            return node_[x].parent = searchAndZipRoot(node_[x].parent);
        }
    }

    void unite(const ll& x,
               const ll& y,
               const ll& weight = 0) {
        auto rx = searchAndZipRoot(x);
        auto ry = searchAndZipRoot(y);
        if(rx != ry) {
            auto yw = weight + calcWeight(x) - calcWeight(y);
            if(node_[rx].rank < node_[ry].rank) {
                std::swap(rx, ry);
                yw *= -1;
            }
            node_[ry].parent  = rx;
            node_[ry].weight  = yw;
            node_[rx].size   += node_[ry].size;
            if(node_[rx].rank == node_[ry].rank) {
                node_[rx].rank++;
            }
        }
    }

    ll calcWeight(const ll& x) {
        searchAndZipRoot(x);
        return node_[x].weight;
    }

    ll calcDiff(const ll& x,
                const ll& y) {
        return std::abs(calcWeight(x) - calcWeight(y));
    }

    ll calcSize(const ll& x) {
        return node_[searchAndZipRoot(x)].size;
    }

    template<class... A>
    bool checkWhetherRootIsSame(const A&... nodes) {
        auto node_list = std::initializer_list<ll>{nodes...};
        if(node_list.size() < 2) return false;
        auto v = searchAndZipRoot(*node_list.begin());
        for(size_t i = 1; i < node_list.size(); i++) {
            if(v != searchAndZipRoot(*(node_list.begin() + i))) return false;
        }
        return true;
    }

private:
    std::vector<Node> node_;
};

/**
 *  最小全域木を求める(Kruskal法)
 *  NOTE: 計算量O(|E|log|V|), Dependencies: comp-Graph, comp-UnionFind
 *  @Return: 最小全域木を返す グラフが非連結の場合、連結成分ごとに最小全域木を構成する
 */
// 使用例
// auto mst = kruskal(g);
// std::cout << mst.getTotalCost() << std::endl;
Graph kruskal(const Graph& g) {
    if(g.edge_type != Graph::Type::Undirected) throw std::logic_error("Graph type is invalid");
    Graph mst(g.vertices.size(), Graph::Type::Undirected);
    std::vector<std::pair<ll, std::pair<int, int>>> mst_e;
    mst_e.reserve(g.edges.size());
    for(size_t i = 0; i < g.edges.size(); i++)
        for(const auto& e : g.edges[i])
            mst_e.emplace_back(make_pair(i, e.first), e.second->cost);
    sort(mst_e.begin(), mst_e.end());
    UnionFind uf(g.vertices.size());
    for(const auto& e : mst_e) {
        if(!uf.checkWhetherRootIsSame(e.second.first, e.second.second)) {
            mst.addEdge(e.second.first, e.second.second, e.first);
            uf.unite(e.second.first, e.second.second);
        }
    }
    return mst;
}

void DFS(Graph&     g,
         const int& index,
         ll&       ans) {
    for(const auto& e : g.edges[index]) {
        if(g.vertices[e.first].cost == 0) {
            g.vertices[e.first].cost = 1;
            ans += e.second->cost;
            DFS(g, e.first, ans);
        }
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N;
    std::cin >> N;

    vector<pair<pair<int, int>, int>> city_prior_x;
    vector<pair<pair<int, int>, int>> city_prior_y;
    REP(i, N) {
        int x, y;
        std::cin >> x >> y;
        city_prior_x.emplace_back(make_pair(x, y), i);
        city_prior_y.emplace_back(make_pair(y, x), i);
    }

    Graph g(N, Graph::Type::Undirected);

    sort(ALL(city_prior_x));
    sort(ALL(city_prior_y));
    for(int i = 0; i < N - 1; i++) {
        g.addEdge(city_prior_x[i].second,
                  city_prior_x[i + 1].second,
                  min(abs(city_prior_x[i].first.first  - city_prior_x[i + 1].first.first),
                      abs(city_prior_x[i].first.second - city_prior_x[i + 1].first.second)));
        g.addEdge(city_prior_y[i].second,
                  city_prior_y[i + 1].second,
                  min(abs(city_prior_y[i].first.first  - city_prior_y[i + 1].first.first),
                      abs(city_prior_y[i].first.second - city_prior_y[i + 1].first.second)));
    }

    auto mst = kruskal(g);

    mst.setCostToAllVertex(0);
    mst.vertices[0].cost = 1;
    ll ans = 0;
    DFS(mst, 0, ans);

    std::cout << ans << std::endl;

    return 0;
}


Compiler output:
a.cc: In function 'int main()':
a.cc:229:9: error: 'class Graph' has no member named 'setCostToAllVertex'; did you mean 'setCostToAllVertices'?
  229 |     mst.setCostToAllVertex(0);
      |         ^~~~~~~~~~~~~~~~~~
      |         setCostToAllVertices
In file included from /usr/include/x86_64-linux-gnu/c++/14/bits/c++allocator.h:33,
                 from /usr/include/c++/14/bits/allocator.h:46,
                 from /usr/include/c++/14/string:43,
                 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/new_allocator.h: In instantiation of 'void std::__new_allocator<_Tp>::construct(_Up*, _Args&& ...) [with _Up = std::pair<long long int, std::pair<int, int> >; _Args = {std::pair<long unsigned int, long long int>, long long int&}; _Tp = std::pair<long long int, std::pair<int, int> >]':
/usr/include/c++/14/bits/alloc_traits.h:575:17:   required from 'static void std::allocator_traits<std::allocator<_CharT> >::construct(allocator_type&, _Up*, _Args&& ...) [with _Up = std::pair<long long int, std::pair<int, int> >; _Args = {std::pair<long unsigned int, long long int>, long long int&}; _Tp = std::pair<long long int, std::pair<int, int> >; allocator_type = std::allocator<std::pair<long long int, std::pair<int, int> > >]'
  575 |           __a.construct(__p, std::forward<_Args>(__args)...);
      |           ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/vector.tcc:117:30:   required from 'std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::emplace_back(_Args&& ...) [with _Args = {std::pair<long unsigned int, long long int>, long long int&}; _Tp = std::pair<long long int, std::pair<int, int> >; _Alloc = std::allocator<std::pair<long long int, std::pair<int, int> > >; reference = std::pair<long long int, std::pair<int, int> >&]'
  117 |             _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
      |             ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  118 |                                      std::forward<_Args>(__args)...);
      |                                      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:172:31:   required from here
  172 |             mst_e.emplace_back(make_pair(i, e.first), e.second->cost);
      |             ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/new_allocator.h:191:11: error: no matching function for call to 'std::pair<long long int, std::pair<int, int> >::pair(std::pair<long unsigned int, long long int>, long long int&)'
  191 |         { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
      |           ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/bits/stl_algobase.h:64,
                 from /usr/include/c++/14/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51:
/usr/include/c++/14/bits/stl_pair.h:913:28: note: candidate: 'template<class _U1, class _U2, typename std::enable_if<(std::_PCC<((! std::is_same<long long int, _U1>::value) || (! std::is_same<std::pair<int, int>, _U2>::value)), long long int, std::pair<int, int> >::_MoveConstructiblePair<_U1, _U2>() && (! std::_PCC<((! std::is_same<long long int, _U1>::value) || (! std::is_same<std::pair<int, int>, _U2>::value)), long long int, std::pair<int, int> >::_ImplicitlyMoveConvertiblePair<_U1, _U2>())), bool>::type <anonymous> > constexpr std::pair<_T1, _T2>::pair(std::pair<_U1, _U2>&&) [with _U2 = _U1; typename std::enable_if<(std::_PCC<((! std::is_same<_T1, _U1>::value) || (! std::is_same<_T2, _U2>::value)), _T1, _T2>::_MoveConstructiblePair<_U1, _U2>() && (! std::_PCC<((! std::is_same<_T1, _U1>::value) || (! std::is_same<_T2, _U2>::value)), _T1, _T2>::_ImplicitlyMoveConvertiblePair<_U1, _U2>())), bool>::type <anonymous> = _U2; _T1 = long long int; _T2 = std::pair<int, int>]'
  913 |         explicit constexpr pair(pair<_U1, _U2>&& __p)
      |                            ^~~~
/usr/include/c++/14/bits/stl_pair.h:913:28: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_pair.h:902:19: note: candidate: 'template<class _U1, class _U2, typename std::enable_if<(std::_PCC<((! std::is_same<long long int, _U1>::value) || (! std::is_same<std::pair<int, int>, _U2>::value)), long long int, std::pair<int, int> >::_MoveConstructiblePair<_U1, _U2>() && std::_PCC<((! std::is_same<long long int, _U1>::value) || (! std::is_same<std::pair<int, int>, _U2>::value)), long long int, std::pair<int, int> >::_ImplicitlyMoveConvertiblePair<_U1, _U2>()), bool>::type <anonymous> > constexpr std::pair<_T1, _T2>::pair(std::pair<_U1, _U2>&&) [with _U2 = _U1; typename std::enable_if<(std::_PCC<((! std::is_same<_T1, _U1>::value) || (! std::is_same<_T2, _U2>::value)), _T1, _T2>::_MoveConstructiblePair<_U1, _U2>() && std::_PCC<((! std::is_same<_T1, _U1>::value) || (! std::is_same<_T2, _U2>::value)), _T1, _T2>::_ImplicitlyMoveConvertiblePair<_U1, _U2>()), bool>::type <anonymous> = _U2; _T1 = long long int; _T2 = std::pair<int, int>]'
  902 |         constexpr pair(pair<_U1, _U2>&& __p)
      |                   ^~~~
/usr/include/c++/14/bits/stl_pair.h:902:19: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_pair.h:891:28: note: candidate: 'template<class _U1, class _U2, typename std::enable_if<(_MoveConstructiblePair<_U1, _U2>() && (! _ImplicitlyMoveConvertiblePair<_U1, _U2>())), bool>::type <anonymous> > constexpr std::pair<_T1, _T2>::pair(_U1&&, _U2&&) [with _U2 = _U1; typename std::enable_if<(std::_PCC<true, _T1, _T2>::_MoveConstructiblePair<_U1, _U2>() && (! std::_PCC<true, _T1, _T2>::_ImplicitlyMoveConvertiblePair<_U1, _U2>())), bool>::type <anonymous> = _U2; _T1 = long long int; _T2 = std::pair<int, int>]'
  891 |         explicit constexpr pair(_U1&& __x, _U2&& __y)
      |                            ^~~~
/usr/include/c++/14/bits/stl_pair.h:891:28: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_pair.h:890:38: error: no type named 'type' in 'struct std::enable_if<false, bool>'
  890 |                          bool>::type=false>
      |                                      ^~~~~
/usr/include/c++/14/bits/stl_pair.h:881:19: note: candidate: 'template<class _U1, class _U2, typename std::enable_if<(_MoveConstructiblePair<_U1, _U2>() && _ImplicitlyMoveConvertiblePair<_U1, _U2>()), bool>::type <anonymous> > constexpr std::pair<_T1, _T2>::pair(_U1&&, _U2&&) [with _U2 = _U1; typename std::enable_if<(std::_PCC<true, _T1, _T2>::_MoveConstructiblePair<_U1, _U2>() && std::_PCC<true, _T1, _T2>::_ImplicitlyMoveConvertiblePair<_U1, _U2>()), bool>::type <anonymous> = _U2; _T1 = long long int; _T2 = std::pair<int, int>]'
  881 |         constexpr pair(_U1&& __x, _U2&& __y)
      |                   ^~~~
/usr/include/c++/14/bits/stl_pair.h:881:19: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_pair.h:880:38: error: no type named 'type' in 'struct std::enable_if<false, bool>'
  880 |                          bool>::type=true>
      |                                      ^~~~
/usr/include/c++/14/bits/stl_pair.h:869:9: note: candidate: 'template<class _U2, typename std::enable_if<std::__and_<std::is_pointer<long long int>, std::__not_<std::is_reference<_Tp> >, std::is_constructible<std::pair<int, int>, _U2>, std::__not_<std::is_constructible<std::pair<int, int>, const _U1&> >, std::__not_<std::is_convertible<_U2, std::pair<int, int> > > >::value, bool>::type <anonymous> > constexpr std::pair<_T1, _T2>::pair(__zero_as_null_pointer_constant, _U2&&, ...) [with typename std::enable_if<std::__and_<std::is_pointer<_Tp>, std::__not_<std::is_reference<_U1> >, std::is_constructible<_T2, _U2>, std::__not_<std::is_constructible<_T1, const _U1&> >, std::__not_<std::is_convertible<_U2, _T2> > >::value, bool>::type <anonymous> = _U2; _T1 = long long int; _T2 = std::pair<int, int>]'
  869 |         pair(__zero_as_null_pointer_constant, _U2&& __y, ...)
      |         ^~~~
/usr/include/c++/14/bits/stl_pair.h:869:9: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_pair.h:866:38: error: no type named 'type' in 'struct std::enable_if<false, bool>'
  866 |                              bool> = false>
      |                                      ^~~~~
/usr/include/c++/14/bits/stl_pair.h:856:9: note: candidate: 'template<class _U2, typename std::enable_if<std::__and_<std::is_pointer<long long int>, std::__not_<std::is_reference<_Tp> >, std::is_constructible<std::pair<int, int>, _U2>, std::__not_<std::is_constructible<std::pair<int, int>, const _U1&> >, std::is_convertible<_U2, std::pair<int, int> > >::value, bool>::type <anonymous> > constexpr std::pair<_T1, _T2>::pair(__zero_as_null_pointer_constant, _U2&&, ...) [with typename std::enable_if<std::__and_<std::is_pointer<_Tp>, std::__not_<std::is_reference<_U1> >, std::is_constructible<_T2, _U2>, std::__not_<std::is_constructible<_T1, const _U1&> >, std::is_convertible<_U2, _T2> >::value, bool>::type <anonymous> = _U2; _T1 = long long int; _T2 = std::pair<int, int>]'
  856 |         pair(__zero_as_null_pointer_constant, _U2&& __y, ...)
      |         ^~~~
/usr/include/c++/14/bits/stl_pair.h:856:9: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_pair.h:853:38: error: no type named 'type' in 'struct std::enable_if<false, bool>'
  853 |                              bool> = true>
      |                                      ^~~~
/usr/include/c++/14/bits/stl_pair.h:843:9: note: candidate: 'template<class _U1, typename std::enable_if<std::__and_<std::__not_<std::is_reference<_Tp> >, std::is_pointer<std::pair<int, int> >, std::is_constructible<long long int, _U2>, std::__not_<std::is_constructible<long long int, const _U1&> >, std::__not_<std::is_convertible<_U2, long long int> > >::value, bool>::type <anonymous> > constexpr std::pair<_T1, _T2>::pair(_U1&&, __zero_as_null_pointer_constant, ...) [with typename std::enable_if<std::__and_<std::__not_<std::is_reference<_U1> >, std::is_pointer<_T2>, std::is_constructible<_T1, _U1>, std::__not_<std::is_