graph/minimum_spanning_tree/Kruskal.cpp

View this file on GitHub
Last update: 2026-01-31 20:47:40+08:00

Verified with

Code

//#include "ds/DSU/DSU.cpp"

template<bool sorted = false, integral T>
auto Kruskal(int n, vector<tuple<int, int, T>> &e) {
  vi ord;
  if constexpr (sorted) {
    ord.resize(n);
    iota(ord.begin(), ord.end(), 0ll);
  } else {
    ord = argSort(e, [](tuple<int, int, T> &t) { return get<2>(t); });
  }

  T cost = 0;
  vi eid;
  DSU dsu(n);
  for(int i : ord) {
    auto [u, v, w] = e[i];
    if (dsu.merge(u, v))
      cost += w, eid.emplace_back(i);
  }

  return pair(cost, eid);
}

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

template<bool sorted = false, integral T>
auto Kruskal(int n, vector<tuple<int, int, T>> &e) {
  vi ord;
  if constexpr (sorted) {
    ord.resize(n);
    iota(ord.begin(), ord.end(), 0ll);
  } else {
    ord = argSort(e, [](tuple<int, int, T> &t) { return get<2>(t); });
  }

  T cost = 0;
  vi eid;
  DSU dsu(n);
  for(int i : ord) {
    auto [u, v, w] = e[i];
    if (dsu.merge(u, v))
      cost += w, eid.emplace_back(i);
  }

  return pair(cost, eid);
}