leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

MST_pq.cpp (384B)

0 // Kruskal's Algorithm 1 // Require UnionFind 2 3 int MST(int n, priority_queue<edge> &pq) { 4 int weight = 0; 5 6 UnionFind uf(n); 7 while (!pq.empty() && uf.count() != 1) { 8 const auto &e = pq.top(); 9 pq.pop(); 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 }