kruskal.cpp
Bài toán
Tìm cây khung nhỏ nhất của đồ thị vô hướng liên thông.
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int par[230997];
int anc(int p) {
if (par[p] == p)
return p;
else
return par[p] = anc(par[p]);
}
void join(int p, int q) { par[anc(p)] = anc(q); }
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
#define X first
#define Y second
vector<iii> edge;
int n, m;
main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
par[i] = i;
while (m--) {
int p, q, w;
scanf("%d%d%d", &p, &q, &w);
edge.push_back(iii(w, ii(p, q)));
}
sort(edge.begin(), edge.end());
vector<iii>::iterator it;
int r = 0;
for (it = edge.begin(); it != edge.end(); it++) {
if (anc(it->Y.X) != anc(it->Y.Y)) {
join(it->Y.X, it->Y.Y);
r += it->X;
}
}
printf("%d\n", r);
}