题解 | #最小生成树#

Prim的解法（记录一下）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int n户人家的村庄
     * @param m int m条路
     * @param cost intvector<vector<>> 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int
     */
    int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
      // prim
      unordered_set<int> node;  // 不重复结点
      int ans = 0;  // 统计权值
      sort(cost.begin(), cost.end(), 
           [&](std::vector<int> &x1, std::vector<int> &x2) -> bool 
           {return x1[2] < x2[2];});   // 升序排序
      // 确定头个结点
      node.insert(cost[0][0]);    // 结点加入集合
      node.insert(cost[0][1]);
      ans += cost[0][2];   // 权值
      
      while (1) {
        if (node.size() == n) {  // 所有结点被访问
          break;   
        }
        
        for (auto it = cost.begin(); it != cost.end(); it++) {
          // 划分集合的方式确保不会形成回路
          if ((node.find((*it)[0]) != node.end()) && node.find((*it)[1]) == node.end()
             || node.find((*it)[0]) == node.end() && node.find((*it)[1]) != node.end()) {
            node.insert((*it)[0]);
            node.insert((*it)[1]);
            ans += (*it)[2];
            break;   // 加入结点后下一个最小权值可能在迭代器前方，不能继续遍历
          }
        }
      }
     return ans; 
    }
};