最小生成树

[TieMuZhen]

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 返回最小的花费代价使得这n户人家连接起来
 * @param n int n户人家的村庄
 * @param m int m条路
 * @param cost int二维数组 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
 * @return int
 */
let parents = [];
function find_root(x){
    let root = x;
    if(parents[x] != -1){
        root = find_root(parents[x]);
    }
    return root;
}
function miniSpanningTree( n ,  m ,  cost ) {
    let sum = 0, num = 0;
    parents = new Array(n + 1).fill(-1); // 对应的顶点不是从0开始而是从1开始，所以数组大小应为n+1
    cost.sort((a, b) => {return a[2] - b[2]}); // 按照边的权重排序从小到大
    for(let i = 0; i < m; i++){
        if(find_root(cost[i][0]) != find_root(cost[i][1]) && num < n){
            parents[find_root(cost[i][0])] = find_root(cost[i][1]); // 找根节点后再修改parents
            sum += cost[i][2];
            num++;
        }
    }
    return sum;
}