This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM \
"https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/2/GRL_2_A"
#include <bits/stdc++.h>
using namespace std;
#include "../../src/graph/kruskul.hpp"
#include "../../src/graph/template.hpp"
int main() {
int V, E;
cin >> V >> E;
Kruskal<long long> kruskal(V);
for (int i = 0; i < E; ++i) {
int s, t, d;
cin >> s >> t >> d;
kruskal.add_edge(s, t, d);
}
kruskal.build();
cout << kruskal.get_cost_sum() << endl;
return 0;
}
#line 1 "test/aoj/grl_2_a.test.cpp"
#define PROBLEM \
"https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/2/GRL_2_A"
#include <bits/stdc++.h>
using namespace std;
#line 2 "src/graph/kruskul.hpp"
#line 4 "src/graph/kruskul.hpp"
using namespace std;
#line 2 "src/structure/union_find_tree.hpp"
#line 4 "src/structure/union_find_tree.hpp"
using namespace std;
struct UnionFindTree {
private:
int n;
vector<int> parent, rank;
public:
UnionFindTree(int n) : n(n), parent(n, -1), rank(n, 0) {}
int root(int x) {
if (parent[x] == -1) {
return x;
}
return parent[x] = root(parent[x]);
}
void unite(int x, int y) {
x = root(x);
y = root(y);
if (x == y) {
return;
}
if (rank[x] < rank[y]) {
swap(x, y);
}
if (rank[x] == rank[y]) {
++rank[x];
}
parent[y] = x;
}
bool is_same(int x, int y) { return root(x) == root(y); }
vector<vector<int>> groups() {
vector<vector<int>> ret(n);
for (int i = 0; i < n; i++) {
ret[root(i)].emplace_back(i);
}
ret.erase(remove_if(begin(ret), end(ret),
[&](const vector<int> &v) { return v.empty(); }),
end(ret));
return ret;
}
};
#line 2 "src/graph/template.hpp"
#line 4 "src/graph/template.hpp"
using namespace std;
template <typename T = long long> struct Edge {
int from, to;
T cost;
Edge(int from, int to, T cost = 1) : from(from), to(to), cost(cost) {}
};
template <typename T = long long> using Edges = vector<Edge<T>>;
template <typename T = long long> using Graph = vector<Edges<T>>;
template <typename T = long long> using Matrix = vector<vector<T>>;
#line 8 "src/graph/kruskul.hpp"
template <typename T> struct Kruskal {
private:
int v;
Edges<T> es;
UnionFindTree uft;
long long cost_sum = 0;
Edges<T> ans_es;
public:
Kruskal(int v) : v(v), uft(v) {}
void add_edge(int from, int to, T cost) { es.emplace_back(from, to, cost); }
void build() {
sort(es.begin(), es.end(), [](const Edge<T> &e1, const Edge<T> &e2) {
return e1.cost < e2.cost;
});
for (Edge<T> &e : es) {
if (!uft.is_same(e.from, e.to)) {
uft.unite(e.from, e.to);
cost_sum += e.cost;
ans_es.emplace_back(e);
}
}
}
T get_cost_sum() { return cost_sum; }
Edges<T> get_edges() { return ans_es; }
};
#line 9 "test/aoj/grl_2_a.test.cpp"
int main() {
int V, E;
cin >> V >> E;
Kruskal<long long> kruskal(V);
for (int i = 0; i < E; ++i) {
int s, t, d;
cin >> s >> t >> d;
kruskal.add_edge(s, t, d);
}
kruskal.build();
cout << kruskal.get_cost_sum() << endl;
return 0;
}