library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub yuruhi/library

:heavy_check_mark: test/Kruskal.test.cpp

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/all/GRL_2_A"
#include "./../Graph/Kruskal.cpp"
#include <iostream>
using namespace std;

int main() {
	int n, m;
	cin >> n >> m;
	Edges edges(m);
	for (int i = 0; i < m; ++i) {
		int s, t;
		Weight d;
		cin >> s >> t >> d;
		edges[i] = Edge2(s, t, d);
	}

	cout << Kruskal(n, edges) << '\n';
}
#line 1 "test/Kruskal.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/all/GRL_2_A"
#line 2 "Graph/GraphTemplate.cpp"
#include <vector>
#include <utility>
#include <iostream>
#include <limits>

using Weight = long long;
constexpr Weight INF = std::numeric_limits<Weight>::max();
struct Edge {
	int to;
	Weight cost;
	Edge() : to(-1), cost(-1) {}
	Edge(int _to, Weight _cost = 1) : to(_to), cost(_cost) {}
	friend bool operator<(const Edge& e1, const Edge& e2) {
		return e1.cost < e2.cost;
	}
	friend bool operator>(const Edge& e1, const Edge& e2) {
		return e1.cost > e2.cost;
	}
	friend std::ostream& operator<<(std::ostream& os, const Edge& e) {
		return os << "->" << e.to << '(' << e.cost << ')';
	}
};
using UnWeightedGraph = std::vector<std::vector<int>>;
using Graph = std::vector<std::vector<Edge>>;
struct Edge2 {
	int from, to;
	Weight cost;
	Edge2() : from(-1), to(-1), cost(0) {}
	Edge2(int _from, int _to, Weight _cost) : from(_from), to(_to), cost(_cost) {}
	friend bool operator<(const Edge2& e1, const Edge2& e2) {
		return e1.cost < e2.cost;
	}
	friend bool operator>(const Edge2& e1, const Edge2& e2) {
		return e1.cost > e2.cost;
	}
	friend std::ostream& operator<<(std::ostream& os, const Edge2& e) {
		return os << e.from << "->" << e.to << '(' << e.cost << ')';
	}
};
using UnWeightedEdges = std::vector<std::pair<int, int>>;
using Edges = std::vector<Edge2>;
using Matrix = std::vector<std::vector<Weight>>;

auto add_edge(UnWeightedGraph& graph, int v, int u) {
	graph[v].push_back(u);
	graph[u].push_back(v);
}
auto add_edge(Graph& graph, int v, int u, Weight cost) {
	graph[v].emplace_back(u, cost);
	graph[u].emplace_back(v, cost);
}
auto to_graph(const UnWeightedGraph& graph, Weight cost = 1) {
	Graph result(graph.size());
	for (std::size_t i = 0; i < graph.size(); ++i) {
		for (int v : graph[i]) {
			result[i].emplace_back(v, cost);
		}
	}
	return result;
}
auto to_unweighted_graph(const Graph& graph) {
	UnWeightedGraph result(graph.size());
	for (std::size_t i = 0; i < graph.size(); ++i) {
		for (auto [v, cost] : graph[i]) {
			result[i].push_back(v);
		}
	}
	return result;
}
auto to_edges(const UnWeightedGraph& graph, bool unique = false) {
	std::vector<std::pair<int, int>> edges;
	for (std::size_t i = 0; i < graph.size(); ++i) {
		for (int v : graph[i]) {
			if (!unique || static_cast<int>(i) < v) edges.emplace_back(i, v);
		}
	}
	return edges;
}
auto to_edges(const Graph& graph) {
	Edges edges;
	for (std::size_t i = 0; i < graph.size(); ++i) {
		for (auto [v, cost] : graph[i]) {
			edges.emplace_back(i, v, cost);
		}
	}
	return edges;
}
#line 4 "DataStructure/UnionFind.cpp"
#include <algorithm>

class UnionFind {
	std::size_t n;
	std::vector<int> data_m;
	int count_components_m;

public:
	UnionFind(int _n = 0) {
		init(_n);
	}
	void init(int _n) {
		n = _n;
		data_m.assign(n, -1);
		count_components_m = n;
	}
	int root(int x) {
		return data_m[x] < 0 ? x : data_m[x] = root(data_m[x]);
	}
	bool same(int x, int y) {
		return root(x) == root(y);
	}
	bool unite(int x, int y) {
		x = root(x);
		y = root(y);
		if (x == y) {
			return false;
		}
		if (data_m[x] > data_m[y]) {
			std::swap(x, y);
		}
		data_m[x] += data_m[y];
		data_m[y] = x;
		count_components_m--;
		return true;
	}
	int size(int x) {
		return -data_m[root(x)];
	}
	int count_components() const {
		return count_components_m;
	}
	std::vector<int> roots() {
		std::vector<int> result;
		for (std::size_t i = 0; i < n; ++i) {
			if (root(i) == static_cast<int>(i)) result.push_back(i);
		}
		return result;
	}
	std::vector<std::vector<int>> groups() {
		std::vector<int> root_buf(n), group_size(n);
		for (std::size_t i = 0; i < n; i++) {
			root_buf[i] = root(i);
			group_size[root_buf[i]]++;
		}
		std::vector<std::vector<int>> result(n);
		for (std::size_t i = 0; i < n; i++) {
			result[i].reserve(group_size[i]);
		}
		for (std::size_t i = 0; i < n; i++) {
			result[root_buf[i]].push_back(i);
		}
		result.erase(std::remove_if(result.begin(), result.end(),
		                            [&](const std::vector<int>& v) { return v.empty(); }),
		             result.end());
		return result;
	}
};
#line 5 "Graph/Kruskal.cpp"

Weight Kruskal(int V, Edges& graph) {
	std::sort(graph.begin(), graph.end(),
	          [](const Edge2& e1, const Edge2& e2) { return e1.cost < e2.cost; });
	Weight result = 0;
	UnionFind uf(V);
	for (auto e : graph) {
		if (uf.unite(e.from, e.to)) {
			result += e.cost;
		}
	}
	return result;
}
#line 4 "test/Kruskal.test.cpp"
using namespace std;

int main() {
	int n, m;
	cin >> n >> m;
	Edges edges(m);
	for (int i = 0; i < m; ++i) {
		int s, t;
		Weight d;
		cin >> s >> t >> d;
		edges[i] = Edge2(s, t, d);
	}

	cout << Kruskal(n, edges) << '\n';
}
Back to top page