test/graph/kruskal/aoj_grl_2_a.test.cpp

View this file on GitHub
Last update: 2024-10-03 00:41:55+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/2/GRL_2_A

Depends on

Code

// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/2/GRL_2_A

#include "src/graph/kruskal.hpp"

#include <iostream>

using namespace std;

int main() {
	int v, e;
	cin >> v >> e;
	Kruskal<int> k(v);
	for (int i = 0; i < e; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		k.add_edge(a, b, c);
	}
	cout << k.mst_cost() << endl;

	return 0;
}

#line 1 "test/graph/kruskal/aoj_grl_2_a.test.cpp"
// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/2/GRL_2_A

#line 1 "src/graph/kruskal.hpp"



#line 1 "src/datastructure/disjoint_set_union.hpp"



#include <numeric>
#include <utility>
#include <vector>

class DisjointSetUnion {
private:
	std::vector<int> rank, size, p;
	int num{};

public:
	DisjointSetUnion(int n) : rank(n), size(n, 1), p(n), num(n) {
		std::iota(p.begin(), p.end(), 0);
	}

	bool same(int x, int y) { return root(x) == root(y); }

	void unite(int x, int y) {
		x = root(x);
		y = root(y);
		if (x == y) return;
		--num;
		if (rank[x] < rank[y]) std::swap(x, y);
		if (rank[x] == rank[y]) ++rank[x];
		p[y] = x;
		size[x] += size[y];
	}

	int root(int x) { return p[x] == x ? x : p[x] = root(p[x]); }

	int get_size(int x) { return size[root(x)]; }

	[[nodiscard]] int forest_size() const { return num; }
};


#line 5 "src/graph/kruskal.hpp"

#include <algorithm>
#line 8 "src/graph/kruskal.hpp"

template<class T>
class Kruskal {
private:
	struct Edge {
		int from, to;
		T cost;

		Edge(int from, int to, T cost) : from(from), to(to), cost(cost) {}

		bool operator<(Edge const &a) { return cost < a.cost; }
	};

	int n;
	std::vector<Edge> g;

public:
	Kruskal(int n) : n(n) {}

	void add_edge(int from, int to, T cost) { g.emplace_back(from, to, cost); }

	T mst_cost() {
		T cost = 0;
		std::sort(g.begin(), g.end());
		DisjointSetUnion dsu(n);
		cost = 0;
		for (Edge const &e : g) {
			if (!dsu.same(e.from, e.to)) {
				cost += e.cost;
				dsu.unite(e.from, e.to);
			}
		}
		return cost;
	}
};


#line 4 "test/graph/kruskal/aoj_grl_2_a.test.cpp"

#include <iostream>

using namespace std;

int main() {
	int v, e;
	cin >> v >> e;
	Kruskal<int> k(v);
	for (int i = 0; i < e; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		k.add_edge(a, b, c);
	}
	cout << k.mst_cost() << endl;

	return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample1.in	AC	14 ms	7 MB
g++	00_sample2.in	AC	13 ms	7 MB
g++	critical1.in	AC	12 ms	7 MB
g++	critical2.in	AC	21 ms	8 MB
g++	critical3.in	AC	84 ms	10 MB
g++	out1.in	AC	13 ms	7 MB
g++	out10.in	AC	87 ms	11 MB
g++	out11.in	AC	35 ms	8 MB
g++	out12.in	AC	51 ms	9 MB
g++	out13.in	AC	43 ms	9 MB
g++	out14.in	AC	49 ms	9 MB
g++	out15.in	AC	38 ms	8 MB
g++	out2.in	AC	13 ms	7 MB
g++	out3.in	AC	13 ms	7 MB
g++	out4.in	AC	13 ms	7 MB
g++	out5.in	AC	13 ms	7 MB
g++	out6.in	AC	88 ms	11 MB
g++	out7.in	AC	87 ms	11 MB
g++	out8.in	AC	87 ms	11 MB
g++	out9.in	AC	87 ms	11 MB
clang++	00_sample1.in	AC	12 ms	13 MB
clang++	00_sample2.in	AC	12 ms	11 MB
clang++	critical1.in	AC	11 ms	9 MB
clang++	critical2.in	AC	21 ms	10 MB
clang++	critical3.in	AC	101 ms	11 MB
clang++	out1.in	AC	12 ms	9 MB
clang++	out10.in	AC	100 ms	15 MB
clang++	out11.in	AC	37 ms	13 MB
clang++	out12.in	AC	57 ms	11 MB
clang++	out13.in	AC	48 ms	11 MB
clang++	out14.in	AC	56 ms	17 MB
clang++	out15.in	AC	42 ms	11 MB
clang++	out2.in	AC	12 ms	13 MB
clang++	out3.in	AC	12 ms	13 MB
clang++	out4.in	AC	12 ms	9 MB
clang++	out5.in	AC	12 ms	9 MB
clang++	out6.in	AC	101 ms	15 MB
clang++	out7.in	AC	117 ms	15 MB
clang++	out8.in	AC	100 ms	15 MB
clang++	out9.in	AC	102 ms	17 MB