题解 | #最小生成树#

mark

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int n户人家的村庄
     * @param m int m条路
     * @param cost intvector<vector<>> 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int
     */
  
    // 并查集找祖宗
    int find_parent(std::vector<int> &parent, int x) {
      if (parent[x] != x) {
        parent[x] = find_parent(parent, parent[x]);
      }
      return parent[x];
    }
  
    int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
      // kruskal
      
      // 升序排序
      sort(cost.begin(), cost.end(), 
           [&](std::vector<int> &x1, std::vector<int> &x2) -> bool {return x1[2] < x2[2];});
      
      // 并查集集合，各结点编号未知（可能从1开始）多一位
      // 前提是村庄从0或1开始编号
      std::vector<int> parent(n+1);
      
      // 祖宗初始化为自身（各自是一个集合）
      for (int i = 0; i <= n; i++) {
        parent[i] = i;
      }
      
      int ans = 0;  // 权值
      
      for (int i = 0; i < cost.size(); i++) {
        // 找各自结点的祖宗
        int parent_1 = find_parent(parent, cost[i][0]);
        int parent_2 = find_parent(parent, cost[i][1]);
        
        // 不在同一集合则连接，同时更新祖宗和权值
        if (parent_1 != parent_2) {
          ans += cost[i][2];
          // 只需要改祖宗即可
          parent[parent_1] = parent_2;  // 指向同一个祖宗
        }
      }
      
      return ans;
    }
};