Language: C++

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
 
// UnionFind木
// 素集合データ構造というデータ構造です
// いくつかの対象が集合に分類されている状況で
// 2つの要素が同じ集合にいるのか、それとも違う集合にいるのか
// ということを効率的に調べる機能があります
class UnionFind {
private:
  std::vector<int> parent; // あるデータの親
  std::vector<int> sizes;  // あるデータが属する木のサイズ
 
public:
  // コンストラクタ
  // データ一つ一つを木とし、親は自分自身に初期化する
  UnionFind(int n)
    : parent(n)
    , sizes(n, 1)
  {
    for (int i = 0; i < n; ++i) {
      parent[i] = i;
    }
  }
 
  // データxが属する木の根ノードを取得
  // findだがunion-find木の仕組み的に内部で破壊的更新を伴う
  int find(int x) {
    // 親と自分が同じであることが
    // 自分がルートノードであるということ
    if( x == parent[x] ) {
      return x;
    }

    // 経路を圧縮するため調べた辺を根に直接繋ぎ直す
    parent[x] = find(parent[x]);
    return parent[x];
  }
 
  // 2つのデータx, yが属する木をマージする
  void unite(int x, int y) {
    // それぞれのデータの根ノードを取得
    int root_x = find(x);
    int root_y = find(y);
 
    // x, yが同じ木に属するならマージしない
    if (root_x == root_y) return;
 
    // xの木がyの木より大きくなるようにする
    if (sizes[root_x] < sizes[root_y]) {
      std::swap(root_x, root_y);
    }
 
    // xがyの親になるようにマージする
    parent[root_y] = root_x;
    sizes[root_x] += sizes[root_y];
  }
 
  // 2つのデータx, yが同じ木に属するかどうか
  bool same(int x, int y) {
    return (find(x) == find(y));
  }
 
  // データxの属する木のサイズを返す
  int size(int x) {
    return sizes[find(x)];
  }
};
 
// 頂点a, bを繋ぐコストcostの無向辺
class Edge {
  int a, b, cost;
 
  // コストで順序を決める(ソートのときに使われる)
  bool operator<(const Edge &o) const {
    return cost < o.cost;
  }
};
 
// 頂点数と辺集合の組として定義したグラフ
public Graph {
private:
  int n; // 頂点数
  std::vector<Edge> edges; // 辺集合

public:
  // コンストラクタ
  // 頂点数nのグラフを考える
  Graph(int n) : n(n) { }

  // 辺を追加
  void add_edge(const Edge& edge) {
    edges.push_back( edge );
  }
 
  // クラスカル法は最小全域木と言うものを調べるアルゴリズムです
  // クラスカル法を効率的に回すと
  int kruskal() {
    // costの小さい辺から繫いでいくので、昇順にソートしておく
    sort(edges.begin(), edges.end());
 
    // UnionFind木を使うと同じ集合にいることを確認できます
    // これを使って「繋がってるノード」をすべて1つの集合にいることにします
    // 最初の状態では「どれも繋がっていません」が
    // エッジで繋いだ2つのノードは、同じ集合にいることにしてしまいます
    // 辺を追加するときに、すでにつながっているノード同士を繋ぐということが閉路ができる条件なので
    // 閉路を作らないようにつながっていないノードを繋ぐということを繰り返す
    UnionFind uf(n);
    int min_cost = 0;
    for (size_t i = 0; i < edges.size(); ++i) {
      Edge e = edges[i];
      if (!uf.same(e.a, e.b)) {
        min_cost += e.cost;
        uf.unite(e.a, e.b);
      }
    }
 
    return min_cost;
  }
};
 
int main() {
  // 街の数
  int N; 
  // i番目の街のx, y座標をそれぞれ分けて持つ
  std::pair<int, int> x[N], y[N];

  // 入力
  std::cin >> N;
  for (size_t i = 0; i < N; ++i) {
    std::cin >> x[i].first >> y[i].first;
    x[i].second = i;
    y[i].second = i;
  }
 
  // 式 min( |a-c|, |b-d| ) を検討してみると
  // - "x軸側で一番近い"街が正方向・負方向に1つずつ
  // - "y軸側で一番近い"街が正方向・負方向に1つずつ
  // の4つだけがそれぞれの街に存在することがわかります。
  //
  // また隣り合う街はどちらから繋いでも同じです。
  // ということは問題は無向辺グラフということになります。
  //
  // これは言い換えると1つの街について
  // - x軸側について街を並べた並びで後ろに来る街
  // - y軸側について街を並べた並びで後ろに来る街
  // の2つの街だけを検討したら十分なことがわかります
  //
  // そこでx軸y軸それぞれでソートして
  // 隣り合う街を見つけ出します
  sort(x, x + N);
  sort(y, y + N);

  // 問題を
  // - 街をノード
  // - 街の間の道を作る操作をコストを持った辺
  // とするグラフの最小全域木問題に帰着する
  Graph g( N );

  // 後ろの街への辺を作っていく
  for (size_t i = 0; i < N - 1; ++i) {
    // x軸側で1つ後ろの街への辺
    g.add_edge(
      Edge(
        x[i].second,
        x[i+1].second,
        x[i+1].first - x[i].first
      )
    );

    // y軸側で1つ後ろの街への辺
    g.add_edge(
      Edge(
        y[i].second,
        y[i+1].second,
        y[i+1].first - y[i].first
      )
    );
  }
 
  // クラスカル法で最小全域木を作ってコストを見る
  std::cout << g.kruskal() << std::endl;
  return 0;
}

Compiler output:
a.cc:83:1: error: expected unqualified-id before 'public'
   83 | public Graph {
      | ^~~~~~
a.cc: In function 'int main()':
a.cc:160:3: error: 'Graph' was not declared in this scope; did you mean 'isgraph'?
  160 |   Graph g( N );
      |   ^~~~~
      |   isgraph
a.cc:165:5: error: 'g' was not declared in this scope
  165 |     g.add_edge(
      |     ^
a.cc:170:7: error: no matching function for call to 'Edge::Edge(int&, int&, int)'
  170 |       )
      |       ^
a.cc:73:7: note: candidate: 'Edge::Edge()'
   73 | class Edge {
      |       ^~~~
a.cc:73:7: note:   candidate expects 0 arguments, 3 provided
a.cc:73:7: note: candidate: 'constexpr Edge::Edge(const Edge&)'
a.cc:73:7: note:   candidate expects 1 argument, 3 provided
a.cc:73:7: note: candidate: 'constexpr Edge::Edge(Edge&&)'
a.cc:73:7: note:   candidate expects 1 argument, 3 provided
a.cc:179:7: error: no matching function for call to 'Edge::Edge(int&, int&, int)'
  179 |       )
      |       ^
a.cc:73:7: note: candidate: 'Edge::Edge()'
   73 | class Edge {
      |       ^~~~
a.cc:73:7: note:   candidate expects 0 arguments, 3 provided
a.cc:73:7: note: candidate: 'constexpr Edge::Edge(const Edge&)'
a.cc:73:7: note:   candidate expects 1 argument, 3 provided
a.cc:73:7: note: candidate: 'constexpr Edge::Edge(Edge&&)'
a.cc:73:7: note:   candidate expects 1 argument, 3 provided
a.cc:184:16: error: 'g' was not declared in this scope
  184 |   std::cout << g.kruskal() << std::endl;
      |                ^