NyaaLIB::GTL_Kruskal

クラスカル法
重み付き連結グラフの最小全域木を求める　

引数 ARG_Kruskal

• n: 頂点数
• g: 重み付き隣接リスト

戻り値

• 最小全域木となる辺 {from, to, cost} の集合を返す

依存クラス

• DS_UnionFind

https://9871225.hatenablog.com/entry/2022/03/02/202403

#include <bits/stdc++.h>
#include <DS_UnionFind.h>

namespace NyaaLIB
{
	struct ARG_Kruskal
	{
		using ll = long long;
		using wgraph = std::vector<std::vector<std::pair<ll, ll>>>;
		ll n; wgraph &g;
	};

	auto GTL_Kruskal = [&](ARG_Kruskal a) -> std::vector<std::tuple<long long, long long, long long>>
	{
		using ll = long long;
		DS_UnionFind uf(a.n);
		std::vector<std::tuple<ll, ll, ll>> res;
		std::vector<std::tuple<ll, ll, ll>> edges;
		for (ll i = 0; i < a.n; i++) for (auto& e : a.g[i]) edges.push_back({ i, e.first, e.second });
		sort(edges.begin(), edges.end(), [&](const auto& l, const auto& r) { return std::get<2>(l) < std::get<2>(r); });

		for (auto &[f, t, c] : edges)
		{
			if (uf.Same(f, t)) continue;
			uf.Union(f, t);
			res.push_back({ std::min(f, t), std::max(f, t), c });
		}
		return res;
	};
}

実装例
https://atcoder.jp/contests/abc235/submissions/30830231