Language: C++


#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

#define MAX 10000
#define INFTY (1 << 29)

class DisjointSet{
public:
  vector<int> rank, p;

  DisjointSet() {}
  DisjointSet(int size) {
    rank.resize(size, 0);
    p.resize(size, 0);
    for (int i = 0; i < size; i++) {
      makeSet(i);
    }
  }

  void makeSet(int x) {
    p[x] = x;
    rank[x] = 0;
  }

  bool same(int x, int y) {
    return findSet(x) == findSet(y);
  }

  void unite(int x, int y) {
    link(findSet(x), findSet(y));
  }

  void link(int x, int y) {
    if (rank[x] > rank[y]) {
      p[y] = x;
    } else {
      p[x] = y;
      if (rank[x] == rank[y]) {
        rank[y]++;
      }
    }
  }

  int findSet(int x) {
    if (x != p[x]) {
      p[x] = findSet(p[x]);
    }
    return p[x];
  }
};

class Edge {
public:
  int source, target, cost;
  Edge(int source = 0, int target = 0, int cost = 0)
    : source(source)
    , target(target)
    , cost(cost) {}

  bool operator < (const Edge& e) const {
    return cost < e.cost;
  }
};

int kruskal(int N, vector<edge> edges) {
  int totalCost = 0;
  sort(edges.begin(), edges.end());

  DisjointSet dset = DisjointSet(N + 1);

  for (int i = 0; i < N; i++) {
    dset.makeSet(i);
  }

  int source, target;
  for (int i = 0; i < edges.size(); i++) {
    Edge e = edges[i];
    if (!dset.same(e.source, e.target)) {
      totalCost += e.cost;
      dset.unite(e.source, e.target);
    }
  }
  return totalCost;
}

int main() {
  int N, M, cost;
  int source, target;

  cin >> N >> M;

  vector<Edge> edges;
  for (int i = 0; i < M; i++) {
    cin >> source >> target >> cost;
    edges.push_back(Edge(source, target, cost));
  }

  cout << kruskal(N, edges) << endl;

  return 0;
}



Compiler output:
a.cc:69:27: error: 'edge' was not declared in this scope; did you mean 'Edge'?
   69 | int kruskal(int N, vector<edge> edges) {
      |                           ^~~~
      |                           Edge
a.cc:69:31: error: template argument 1 is invalid
   69 | int kruskal(int N, vector<edge> edges) {
      |                               ^
a.cc:69:31: error: template argument 2 is invalid
a.cc: In function 'int kruskal(int, int)':
a.cc:71:14: error: request for member 'begin' in 'edges', which is of non-class type 'int'
   71 |   sort(edges.begin(), edges.end());
      |              ^~~~~
a.cc:71:29: error: request for member 'end' in 'edges', which is of non-class type 'int'
   71 |   sort(edges.begin(), edges.end());
      |                             ^~~
a.cc:80:29: error: request for member 'size' in 'edges', which is of non-class type 'int'
   80 |   for (int i = 0; i < edges.size(); i++) {
      |                             ^~~~
a.cc:81:19: error: invalid types 'int[int]' for array subscript
   81 |     Edge e = edges[i];
      |                   ^
a.cc: In function 'int main()':
a.cc:102:22: error: cannot convert 'std::vector<Edge>' to 'int'
  102 |   cout << kruskal(N, edges) << endl;
      |                      ^~~~~
      |                      |
      |                      std::vector<Edge>
a.cc:69:33: note:   initializing argument 2 of 'int kruskal(int, int)'
   69 | int kruskal(int N, vector<edge> edges) {
      |                    ~~~~~~~~~~~~~^~~~~