题解 | 最小生成树

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 返回最小的花费代价使得这n户人家连接起来
 * @param n int整型 n户人家的村庄
 * @param m int整型 m条路
 * @param cost int整型二维数组 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
 * @param costRowLen int cost数组行数
 * @param costColLen int* cost数组列数
 * @return int整型
 */
#include <stdlib.h>
int compare(const void* a, const void* b){
    int* rowA =  *(int**)a; // 强制类型转换
    int* rowB =  *(int**)b;
    return rowA[2] - rowB[2];
}
int find(int* parent,int x){
    if(parent[x]!=x){
        parent[x]=find(parent, parent[x]);
    }
    return parent[x];
}
int miniSpanningTree(int n, int m, int** cost, int costRowLen, int* costColLen) {
    // write code here
    qsort(cost, m, sizeof(cost[0]), compare);
    for(int i=0;i<m;i++){
        printf("%d ",cost[i][2]);
    }
    int* parent=(int*)malloc(sizeof(int)*(n+1));
    for(int i=0;i<=n;i++){
        parent[i]=i;
    }
    int res = 0;
    for(int i=0;i<m;i++){
        int x=cost[i][0];
        int y=cost[i][1];
        int z=cost[i][2];
        int px=find(parent, x);
        int py=find(parent, y);
        if(px!=py){
            res += z;
            parent[px]=py;
        }
    }
    return res;
}