leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

MST_vector.cpp (390B)

      1 // Kruskal's Algorithm
      2 // Require UnionFind
      3 
      4 int get_mst(int n, const vector<edge> &edges) {
      5     int weight = 0;
      6 
      7     UnionFind uf(n);
      8     for (int i = 0; i < edges.size() && uf.count() != 1; i++) {
      9         const auto &e = edges[i];
     10         if (uf.connected(e[0], e[1])) continue;
     11         uf.join(e[0], e[1]);
     12         weight += e[2];
     13     }
     14 
     15     return uf.count() == 1 ? weight : 1e9 + 7;
     16 }