/
Kruskal.hpp
57 lines (56 loc) · 1.22 KB
/
Kruskal.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class UnionFind {
public:
VI par, rank;
UnionFind(int n) {
par = VI(n);
iota(par.begin(), par.end(), 0);
rank = VI(n, 0);
}
int root(int x) {
if (par[x] == x) {
return x;
} else {
return par[x] = root(par[x]);
}
}
void unite(int x, int y) {
x = root(x);
y = root(y);
if (x == y) {
return;
}
if (rank[x] < rank[y]) {
par[x] = y;
} else {
par[y] = x;
if (rank[x] == rank[y]) {
rank[x]++;
}
}
}
bool same(int x, int y) { return root(x) == root(y); }
};
struct edge {
int u, v, cost;
};
bool comp(const edge& e1, const edge& e2) { return e1.cost < e2.cost; }
int kruskal(int V, vector<edge>& es) {
sort(es.begin(), es.end(), comp);
UnionFind uf(V);
int ans = 0;
for (edge e : es) {
if (uf.same(e.u, e.v)) {
continue;
}
uf.unite(e.u, e.v);
ans += e.cost;
}
return ans;
}
signed main() {
int V, E;
cin >> V >> E;
vector<edge> es(E);
REP(i, E) { cin >> es[i].u >> es[i].v >> es[i].cost; }
cout << kruskal(V, es) << endl;
}