Kruskal法(最小全域木)
(graph/kruskal.hpp)

• View this file on GitHub
• Last update: 2023-03-13 15:00:41+09:00
• Include: #include "graph/kruskal.hpp"

説明

• 最小全域木を求める

• 戻り値は全域木の最小コスト

ll kruskal(vector<Edge<T>> &es, int V)

Depends on

• UnionFind (graph/UnionFind.hpp)

Verified with

• test/aoj/GRL/GRL_2_A.test.cpp

Code

#include "UnionFind.hpp"

template <class T>
ll kruskal(vector<Edge<T>> &es, const int n){
  ll res = 0;
  sort(es.begin(), es.end());
  UnionFind tree(n);
  for(const auto &e : es){
    if(!tree.same(e.from, e.to)){
      tree.unite(e.from, e.to);
      res += e.cost;
    }
  }
  return res;
}

#line 1 "graph/UnionFind.hpp"
struct UnionFind {
  private:
  int n;
  public:
  vector<int> d;
  UnionFind(int n): n(n), d(n, -1){}
  int root(int x){
    assert(0 <= x && x < n);
    if(d[x] < 0) return x;
    return d[x] = root(d[x]);
  }
  bool unite(int x, int y){
    x = root(x);
    y = root(y);
    if(x == y) return false;
    if(d[x] > d[y]) swap(x, y);
    d[x] += d[y];
    d[y] = x;
    return true;
  }
  bool same(int x, int y){
    return root(x) == root(y);
  }
  int size(int x){
    return -d[root(x)];
  }
};
#line 2 "graph/kruskal.hpp"

template <class T>
ll kruskal(vector<Edge<T>> &es, const int n){
  ll res = 0;
  sort(es.begin(), es.end());
  UnionFind tree(n);
  for(const auto &e : es){
    if(!tree.same(e.from, e.to)){
      tree.unite(e.from, e.to);
      res += e.cost;
    }
  }
  return res;
}

Back to top page