最小全域木 (クラスカル法)
(graph/mst-kruskal.hpp)

• View this file on GitHub
• Last update: 2021-08-01 23:46:19+09:00
• Include: #include "graph/mst-kruskal.hpp"

Depends on

• Union-Find (datastructure/union-find-tree.hpp)
• graph/template.hpp

Verified with

• test/aoj/GRL_2_A.test.cpp

Code

/**
 * @title 最小全域木 (クラスカル法)
 */
#include <algorithm>
#include "template.hpp"
#include "../datastructure/union-find-tree.hpp"

template< typename T >
T kruscal(int V, Edges< T > &edges) {
  // 最小全域木の重みを返す
  UnionFind uf(V);
  T weight = 0;
  std::sort(edges.begin(), edges.end());
  for (auto e : edges) {
    if (uf.same(e.from, e.to)) continue;
    uf.unite(e.from, e.to);
    weight += e.cost;
  }
  return weight;
}

#line 1 "graph/mst-kruskal.hpp"
/**
 * @title 最小全域木 (クラスカル法)
 */
#include <algorithm>
#line 1 "graph/template.hpp"



#include <iostream>
#include <vector>

template< typename T >
struct Edge {
  int from, to;
  T cost;
  Edge() {}
  Edge(int f, int t) : from(f), to(t), cost(1) {}
  Edge(int f, int t, T c) : from(f), to(t), cost(c) {}
  friend bool operator < (const Edge& lhs, const Edge& rhs) { return lhs.cost < rhs.cost; };
  friend bool operator > (const Edge& lhs, const Edge& rhs) { return rhs < lhs; };
  friend bool operator <= (const Edge& lhs, const Edge& rhs) { return !(lhs > rhs); };
  friend bool operator >= (const Edge& lhs, const Edge& rhs) { return !(lhs < rhs); };
};

template< typename T >
using Edges = std::vector< Edge< T > >;
template< typename T >
using Graph = std::vector< Edges< T > >;

template< typename T >
void debug(Graph<T> &g, int n = -1) {
    if (n == -1) n = g.size();
    for (int i = 0; i < n; ++i) {
        std::cerr << i  << "\t";
        for (auto &e: g[i]) {
            std::cerr << e.to << ",";
        }
        std::cerr << std::endl;
    }
}


#line 1 "datastructure/union-find-tree.hpp"
/**
 * @title Union-Find
 */
#line 5 "datastructure/union-find-tree.hpp"

class UnionFind {
public:
  std::vector<int> data; // sizeとparを同時に管理する
  UnionFind(int size) : data(size, -1) {}
  int find(int x) { return data[x] < 0 ? x : data[x] = find(data[x]); }
  void unite(int x, int y) {
    int px = find(x);
    int py = find(y);
    if (px != py) {
      if (data[py] < data[px]) std::swap(px, py);
      data[px] += data[py]; data[py] = px;
    }
  }
  bool same(int x, int y) { return find(x) == find(y); }
  int size(int x) { return -data[find(x)]; }
};
#line 7 "graph/mst-kruskal.hpp"

template< typename T >
T kruscal(int V, Edges< T > &edges) {
  // 最小全域木の重みを返す
  UnionFind uf(V);
  T weight = 0;
  std::sort(edges.begin(), edges.end());
  for (auto e : edges) {
    if (uf.same(e.from, e.to)) continue;
    uf.unite(e.from, e.to);
    weight += e.cost;
  }
  return weight;
}

Back to top page