kruscal.cc

/*
 * Minimum spanning tree
 * Kruskal's algorithm
 */
#include <iostream>
#include <vector>
#include <algorithm>

class UnionFind {
  private:
    struct node {
      int label;
      node *parent;
      node(int label): parent(nullptr), label(label) {}
    };
    std::vector<node*> elms;
    node *FindRoot(int label) {
      node* e = elms[label];
      while (e->parent != nullptr) e = e->parent;
      return e;
    }
  public:
    UnionFind(size_t num_elements): elms(std::vector<node*>(num_elements)) {
      for (int i= 0; i < num_elements; ++i) elms[i] = new node(i);
    }
    int Find(int x) {
      return FindRoot(x)->label;
    }
    bool Union(int a, int b){
      auto an = FindRoot(a);
      auto bn = FindRoot(b);
      if (an == bn) return false;
      bn->parent = an;
      return true;
    }

    ~UnionFind(){
      for (auto it = elms.begin(); it != elms.end(); ++it) delete *it;
    }
};

struct Edge {
  int a, b;
  int weight;
  Edge() {}
  Edge(int a, int b, int weight): a(a), b(b), weight(weight) {}
};
bool operator<(const Edge &lhs, const Edge &rhs) {
  return lhs.weight < rhs.weight;
}

int main(int argc, char const* argv[])
{
  int Es, Vs;
  std::cin >> Vs >> Es;
  std::vector<Edge> E(Es);
  std::vector<int> V(Vs);
  for (int i = 0; i < Vs; i++) {
    V[i] = i;
  }
  for (int i = 0; i < Es; i++) {
    int a, b, w;
    std::cin >> a >> b >> w;
    E.emplace_back(a, b, w);
    std::push_heap(E.begin(), E.end());
  }
  std::sort_heap(E.begin(), E.end());
  UnionFind uf(Vs);
  int sum = 0;
  for (auto it=E.begin(); it != E.end(); ++it){
    if (uf.Find(it->a) == uf.Find(it->b)) continue;
    uf.Union(it->a, it->b);
    sum += it->weight;
  }
  std::cout << sum << std::endl;
  return 0;
}