#include "Graph/Minimum-Spanning-Tree/kruskal.hpp"
#pragma once #include <algorithm> #include <vector> #include "../graph-template.hpp" #include "../../Data-Structure/Disjoint-Set/union-find.hpp" /** * @brief kruskal() (クラスカル法) */ template <class ResultType, class WeightType> ResultType kruskal(int V, std::vector<Edge<WeightType>>& edges) { ResultType weightSum{}; UnionFind uf(V); std::sort(edges.begin(), edges.end(), [](const auto& e1, const auto& e2) { return e1.weight < e2.weight; }); for (const auto &e : edges) { if (uf.same(e.from, e.to)) continue; uf.unite(e.from, e.to); weightSum += e.weight; } return weightSum; }
#line 2 "Graph/Minimum-Spanning-Tree/kruskal.hpp" #include <algorithm> #include <vector> #line 2 "Graph/graph-template.hpp" #include <cstdint> #line 4 "Graph/graph-template.hpp" #include <iostream> /** * @brief graph-template (Edge, Graph, MatrixGraph) */ //! グラフの辺 (重み付き) template <class T> struct Edge { int from, to; T weight; int id; Edge() = default; constexpr explicit Edge(int to_, const T& weight_) : Edge(-1, to_, weight_, -1) {} constexpr Edge(int from_, int to_, const T& weight_, int id_ = -1) : from(from_) , to(to_) , weight(weight_) , id(id_) {} constexpr const Edge rev() const { return Edge(to, from, weight, id); } template <class Int, std::enable_if_t<std::is_integral<Int>::value, std::nullptr_t> = nullptr> constexpr operator Int() const { return static_cast<Int>(to); } friend std::istream& operator>>(std::istream& is, Edge& e) { return is >> e.from >> e.to >> e.weight; } }; //! グラフの辺 (重みなし) template <> struct Edge<void> { int from, to; int id; Edge() = default; constexpr explicit Edge(int to_) : Edge(-1, to_, -1) {} constexpr Edge(int from_, int to_, int id_ = -1) : from(from_) , to(to_) , id(id_) {} constexpr const Edge rev() const { return Edge(to, from, id); } template <class Int, std::enable_if_t<std::is_integral<Int>::value, std::nullptr_t> = nullptr> constexpr operator Int() const { return static_cast<Int>(to); } friend std::istream& operator>>(std::istream& is, Edge& e) { return is >> e.from >> e.to; } }; template <class T> using Graph = std::vector<std::vector<Edge<T>>>; #line 2 "Data-Structure/Disjoint-Set/union-find.hpp" #include <cassert> #line 5 "Data-Structure/Disjoint-Set/union-find.hpp" #include <utility> #line 7 "Data-Structure/Disjoint-Set/union-find.hpp" /** * @brief Union-Find (素集合データ構造) * @note path-compression + union-by-size */ class UnionFind { private: int n; mutable std::vector<int> p; public: UnionFind() = default; explicit UnionFind(int n_) : n(n_) , p(n_, -1) {} int unite(int x, int y) { x = leader(x), y = leader(y); if (x == y) return x; if (p[y] < p[x]) std::swap(x, y); p[x] += p[y]; p[y] = x; return x; } int leader(int x) const { return p[x] < 0 ? x : p[x] = leader(p[x]); } bool same(int x, int y) const { return leader(x) == leader(y); } int size(int x) const { return -p[leader(x)]; } std::vector<std::vector<int>> groups() const { std::vector<int> leaderBuf(n), groupSize(n); for (int i = 0; i < n; i++) ++groupSize[leaderBuf[i] = leader(i)]; std::vector<std::vector<int>> result(n); for (int i = 0; i < n; i++) result[i].reserve(groupSize[i]); for (int i = 0; i < n; i++) result[leaderBuf[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 7 "Graph/Minimum-Spanning-Tree/kruskal.hpp" /** * @brief kruskal() (クラスカル法) */ template <class ResultType, class WeightType> ResultType kruskal(int V, std::vector<Edge<WeightType>>& edges) { ResultType weightSum{}; UnionFind uf(V); std::sort(edges.begin(), edges.end(), [](const auto& e1, const auto& e2) { return e1.weight < e2.weight; }); for (const auto &e : edges) { if (uf.same(e.from, e.to)) continue; uf.unite(e.from, e.to); weightSum += e.weight; } return weightSum; }