leetcode

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

MST_pq.cpp (384B)

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