#pragma once #include <bits/stdc++.h> using namespace std; #include "../data_structures/unionfind.cpp" // Kruscal // Kruscal法で最小全域森を求める. template <typename T, const T INF> struct Kruscal { struct edge { int a, b; T cost; int id; edge(int a, int b, T c, int id) : a(a), b(b), cost(c), id(id) {} }; int n; int m = 0; vector<edge> edges; vector<int> used_id; Kruscal(int n) : n(n) {} // add_edge // aからbへコストcの辺を張る void add_edge(int a, int b, T c) { edges.emplace_back(a, b, c, m++); } // solve // 最小全域森を求めて, そのコストを返す. // 計算量: O(|E|log|E|) T solve() { used_id.assign(m, 0); sort(edges.begin(), edges.end(), [](const edge &a, const edge &b) { return a.cost < b.cost; }); T ans = T(0); UnionFind uf(n); for (const edge &e : edges) { if (uf.same(e.a, e.b)) continue; ans += e.cost; used_id[e.id] = 1; uf.unite(e.a, e.b); } return ans; } };
#line 2 "graph/kruscal.cpp" #include <bits/stdc++.h> using namespace std; #line 3 "data_structures/unionfind.cpp" using namespace std; // UnionFind // グループを管理するデータ構造 struct UnionFind { int n; vector<int> parents; UnionFind(int n) : n(n) { parents.assign(n, -1); } // find // xの親を返す. // 制約: 0 <= x < n int find(int x) { if (parents[x] < 0) return x; return parents[x] = find(parents[x]); } // unite // xとyを含むグループを併合 // 制約: 0 <= x,y < n void unite(int x, int y) { // xとyの含むグループを併合 int px = find(x); int py = find(y); if (parents[px] > parents[py]) swap(px, py); if (px != py) { parents[px] += parents[py]; parents[py] = px; } } // same // xとyが同じグループにいるか判定 // 制約: 0 <= x,y < n bool same(int x, int y) { return find(x) == find(y); } // size // xと同じグループのメンバーの個数 // 制約: 0 <= x < n int size(int x) { return -parents[find(x)]; } // root // 根を全て列挙する vector<int> root() { vector<int> res; for (int i = 0; i < n; i++) { if (parents[i] < 0) res.push_back(i); } return res; } // group_count // グループの数を返す. int group_count() { // ufのグループの数を数える return (int)root().size(); } }; #line 6 "graph/kruscal.cpp" // Kruscal // Kruscal法で最小全域森を求める. template <typename T, const T INF> struct Kruscal { struct edge { int a, b; T cost; int id; edge(int a, int b, T c, int id) : a(a), b(b), cost(c), id(id) {} }; int n; int m = 0; vector<edge> edges; vector<int> used_id; Kruscal(int n) : n(n) {} // add_edge // aからbへコストcの辺を張る void add_edge(int a, int b, T c) { edges.emplace_back(a, b, c, m++); } // solve // 最小全域森を求めて, そのコストを返す. // 計算量: O(|E|log|E|) T solve() { used_id.assign(m, 0); sort(edges.begin(), edges.end(), [](const edge &a, const edge &b) { return a.cost < b.cost; }); T ans = T(0); UnionFind uf(n); for (const edge &e : edges) { if (uf.same(e.a, e.b)) continue; ans += e.cost; used_id[e.id] = 1; uf.unite(e.a, e.b); } return ans; } };