最小全域木を求める関数を提供
(ugilib/graph/minimum_spanning.hpp)

• View this file on GitHub
• Last update: 2025-09-23 20:38:32+09:00
• Include: #include "ugilib/graph/minimum_spanning.hpp"

Depends on

• ugilib/base/constants.hpp
• ugilib/base/definitions.hpp

Required by

• tests/graph/minimum_spanning.notest.cpp

Code

#pragma once

/**
 * @file minimum_spanning.hpp
 * @brief 最小全域木を求める関数を提供
 *
 * ## 関数一覧
 * - `kruskal(n, edges)` : クラスカル法により最小全域木を求める
*/

#include <bits/stdc++.h>
#include "ugilib/base/constants.hpp"
#include <atcoder/dsu>

using namespace std;

namespace ugilib {
    /**
     * @brief クラスカル法により最小全域木を求める
     * @tparam weight_t 辺の重みの型
     * @param n 頂点数
     * @param edges 辺のリスト. ソートするのでコピー渡し
     * @return 最小全域木の重みと含まれる辺のリスト
     * @note 辺のリストは {重み, {頂点1, 頂点2}} の形式で与える
     * @note 辺のリストは重みの昇順にソートされる
     * @note O(E log E). E は辺の数. ボトルネックはソート
    */
    template <typename weight_t>
    tuple<weight_t, vector<pair<int, int>>> kruskal(int n, vector<pair<weight_t, pair<int, int>>> edges) {
        // ソート
        sort(edges.begin(), edges.end());

        // クラスカル法
        // 重みの小さい順に辺を追加していく
        atcoder::dsu uf(n);
        vector<pair<int, int>> mst_edges;
        weight_t res = 0;
        for (auto [w, e] : edges) {
            auto [u, v] = e;
            if (uf.same(u, v)) continue;
            uf.merge(u, v);
            mst_edges.emplace_back(u, v);
            res += w;
            if (uf.size(u) == n) break;
        }

        // 全域木ができなかった場合
        if (uf.size(0) != n) return {-1, {}};
        // 最小全域木の重みと辺のリストを返す
        return {res, mst_edges};
    }
}

#line 2 "ugilib/graph/minimum_spanning.hpp"

/**
 * @file minimum_spanning.hpp
 * @brief 最小全域木を求める関数を提供
 *
 * ## 関数一覧
 * - `kruskal(n, edges)` : クラスカル法により最小全域木を求める
*/

#include <bits/stdc++.h>
#line 3 "ugilib/base/definitions.hpp"

// old (compat)
using ll = long long;
using ull = unsigned long long;
using ld = long double;

// new
using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using u128 = __uint128_t;
using i8 = int8_t;
using i16 = int16_t;
using i32 = int32_t;
using i64 = int64_t;
using i128 = __int128_t;
using f32 = float;
using f64 = double;
using f128 = long double;

#define rep(i, n) for(size_t i = 0; i < n; i++)  // rep macro
#define all(v) begin(v), end(v)  // all iterator
#line 4 "ugilib/base/constants.hpp"

namespace ugilib::constants {
    template<typename T>
    inline constexpr T INF = std::numeric_limits<T>::max() / 2;
} // namespace ugilib::constants

const ll INF = ugilib::constants::INF<ll>;
#line 13 "ugilib/graph/minimum_spanning.hpp"
#include <atcoder/dsu>

using namespace std;

namespace ugilib {
    /**
     * @brief クラスカル法により最小全域木を求める
     * @tparam weight_t 辺の重みの型
     * @param n 頂点数
     * @param edges 辺のリスト. ソートするのでコピー渡し
     * @return 最小全域木の重みと含まれる辺のリスト
     * @note 辺のリストは {重み, {頂点1, 頂点2}} の形式で与える
     * @note 辺のリストは重みの昇順にソートされる
     * @note O(E log E). E は辺の数. ボトルネックはソート
    */
    template <typename weight_t>
    tuple<weight_t, vector<pair<int, int>>> kruskal(int n, vector<pair<weight_t, pair<int, int>>> edges) {
        // ソート
        sort(edges.begin(), edges.end());

        // クラスカル法
        // 重みの小さい順に辺を追加していく
        atcoder::dsu uf(n);
        vector<pair<int, int>> mst_edges;
        weight_t res = 0;
        for (auto [w, e] : edges) {
            auto [u, v] = e;
            if (uf.same(u, v)) continue;
            uf.merge(u, v);
            mst_edges.emplace_back(u, v);
            res += w;
            if (uf.size(u) == n) break;
        }

        // 全域木ができなかった場合
        if (uf.size(0) != n) return {-1, {}};
        // 最小全域木の重みと辺のリストを返す
        return {res, mst_edges};
    }
}

Back to top page