code/graphs/kruskal.cc

View this file on GitHub
Last update: 2021-06-13 17:53:40+02:00

Depends on

Verified with

tests/aoj/kruskal.minimum_spanning_tree.test.cc

Code

#include "../dataStructures/DSU.cc"
template <typename W, typename C = less<tuple<W, int, int>>>
tuple<bool, W, vi> kruskal(int V, vector<tuple<W, int, int>>& edges, C cmp = C()) {
  sort(ALL(edges), cmp); DSU dsu(V); vi mst;
  W w = 0;
  for (int i = 0; SZ(dsu) > 1 && i < SZ(edges); ++i) {
    auto [d, a, b] = edges[i];
    if (dsu.join(a, b)) mst.pb(i), w += d;
  }
  return mt(SZ(dsu) == 1, w, mst);
}

#line 1 "code/template.cc"
// this line is here for a reason
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define fi first
#define se second
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define endl '\n'
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define SZ(x) (int)(x).size()
#define FOR(a, b, c) for (auto a = (b); (a) < (c); ++(a))
#define F0R(a, b) FOR (a, 0, (b))
template <typename T>
bool ckmin(T& a, const T& b) { return a > b ? a = b, true : false; }
template <typename T>
bool ckmax(T& a, const T& b) { return a < b ? a = b, true : false; }
#ifndef DEBUG
#define DEBUG 0
#endif
#define dout if (DEBUG) cerr
#define dvar(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#line 2 "code/dataStructures/DSU.cc"
struct DSU {
  DSU(int size) : msize(size), data(size, -1) {}
  bool sameSet(int a, int b) { return find(a) == find(b); }
  int find(int x) {
    return data[x] < 0 ? x : data[x] = find(data[x]);
  }
  bool join(int a, int b) {
    a = find(a), b = find(b);
    if (a == b) return false;
    if (data[a] > data[b]) swap(a, b);
    data[a] += data[b], data[b] = a;
    return --msize, true;
  }
  int size() { return msize; }
  int size(int a) { return -data[find(a)]; }
  int msize;
  vi data;
};
#line 2 "code/graphs/kruskal.cc"
template <typename W, typename C = less<tuple<W, int, int>>>
tuple<bool, W, vi> kruskal(int V, vector<tuple<W, int, int>>& edges, C cmp = C()) {
  sort(ALL(edges), cmp); DSU dsu(V); vi mst;
  W w = 0;
  for (int i = 0; SZ(dsu) > 1 && i < SZ(edges); ++i) {
    auto [d, a, b] = edges[i];
    if (dsu.join(a, b)) mst.pb(i), w += d;
  }
  return mt(SZ(dsu) == 1, w, mst);
}