graph/Kruskal.cpp

View this file on GitHub
Last update: 2024-06-29 17:34:40+08:00

Verified with

test/minimum_spanning_tree.test.cpp

Code

//#include "ds/DSU.cpp"

template<class T, bool sorted = false>
pair<T, vector<int>> Kruskal(vector<array<T, 3>> &e, int n) {
  vector<int> id(ssize(e));
  iota(id.begin(), id.end(), 0);
  if constexpr (!sorted)
    ranges::sort(id, {}, [&e](int i) { return e[i][2]; });

  T cost = 0;
  DSU dsu(n);
  vector<int> res;
  for(int i : id) {
    auto [u, v, w] = e[i];
    if (dsu.merge(u, v)) {
      cost += w;
      res.emplace_back(i);
    }
  }
  return make_pair(cost, res);
}

#line 1 "graph/Kruskal.cpp"
//#include "ds/DSU.cpp"

template<class T, bool sorted = false>
pair<T, vector<int>> Kruskal(vector<array<T, 3>> &e, int n) {
  vector<int> id(ssize(e));
  iota(id.begin(), id.end(), 0);
  if constexpr (!sorted)
    ranges::sort(id, {}, [&e](int i) { return e[i][2]; });

  T cost = 0;
  DSU dsu(n);
  vector<int> res;
  for(int i : id) {
    auto [u, v, w] = e[i];
    if (dsu.merge(u, v)) {
      cost += w;
      res.emplace_back(i);
    }
  }
  return make_pair(cost, res);
}