minimum spanning tree

ソースコード

 1#include <vector>
 2#include <algorithm>
 3#include "titan_cpplib/data_structures/union_find.cpp"
 4using namespace std;
 5
 6namespace titan23 {
 7
 8    //! 最小全域木の辺集合を返す
 9    vector<pair<int, int>> minimum_spanning_tree(int n, const vector<pair<int, int>> &E) {
10        titan23::UnionFind uf(n);
11        vector<pair<int, int>> ans;
12        for (const auto &[u, v] : E) {
13            if (uf.same(u, v)) continue;
14            uf.unite(u, v);
15            ans.emplace_back(u, v);
16        }
17        return ans;
18    }
19}  // namespace titan23

仕様

Warning

doxygenfile: Cannot find file “titan_cpplib/graph/minimum_spanning_tree.cpp