kruskal.cc

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cstdint>
 
struct UnionFind {
private:
	std::vector<int64_t> data;
public:
	UnionFind(size_t size);
	bool unionSet(size_t x, size_t y);
	bool findSet(size_t x, size_t y);
	size_t root(size_t x);
	int64_t size(size_t x);
};
 
UnionFind::UnionFind(size_t size) : data(size, -1) {}
 
bool UnionFind::unionSet(size_t x, size_t y) {
	x = root(x);
	y = root(y);
	if(x != y) {
		if(size(x) > size(y))
			std::swap(x, y);
		data[x] += data[y];
		data[y] = x;
	}
	return x != y;
}
 
bool UnionFind::findSet(size_t x, size_t y) {
	return root(x) == root(y);
}
 
size_t UnionFind::root(size_t x) {
	if(data[x] < 0)
		return x;
	else
		return root(data[x]);
}
 
int64_t UnionFind::size(size_t x) {
	return -data[root(x)];
}
 
 
struct Edge {
	size_t start, end;
	int64_t cost;
	bool operator==(const Edge &e) {
		return cost == e.cost;
	}
	bool operator<(const Edge &e) const {
		return cost < e.cost;
	}
};
 
 
auto main(void) -> int {
	using namespace std;
	int32_t N, M; // N = |V|, M = |E|
	cin >> N >> M;
	auto edges = new vector<Edge>(M);
	for(auto it = edges->begin(), eit = edges->end(); it != eit; ++it) {
		// Edge format: start_point end_point cost
		size_t st, ed;
		int64_t c;
		cin >> st >> ed >> c;
		Edge edge{st, ed, c};
		*it = edge;
	}
	sort(edges->begin(), edges->end());
	auto minTree = new vector<Edge>;
	auto uft = new UnionFind(N);
	for(auto it = edges->begin(), eit = edges->end(); it != eit; ++it) {
		auto edge = *it;
		if(!uft->findSet(edge.start, edge.end)) {
			minTree->push_back(edge);
			uft->unionSet(edge.start, edge.end);
		}
	}
	for(auto e : *minTree) {
		cout << e.start << ' ' << e.end << ' ' << e.cost << '\n';
	}
}