题解 | #最小生成树#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 返回最小的花费代价使得这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
 */
//kruskal配mergeSort,如果配buble时间会超
void mergeSort(int** arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        int temp[right - left + 1][ 3];
        int i = left;
        int j = mid + 1;
        int k = 0;
        while (i <= mid && j <= right) {
            if (arr[i][2] < arr[j][2]) {
                temp[k][1] = arr[i][1];
                temp[k][2] = arr[i][2];
                temp[k++][0] = arr[i++][0];
            }

            else {
                temp[k][1] = arr[j][1];
                temp[k][2] = arr[j][2];
                temp[k++][0] = arr[j++][0];
            }
        }
        while (i <= mid) {
            temp[k][1] = arr[i][1];
            temp[k][2] = arr[i][2];
            temp[k++][0] = arr[i++][0];
        }

        while (j <= right) {
            temp[k][1] = arr[j][1];
            temp[k][2] = arr[j][2];
            temp[k++][0] = arr[j++][0];
        }


        for (int i = 0; i < k; i++) {
            arr[left + i][0] = temp[i][0];
            arr[left + i][1] = temp[i][1];
            arr[left + i][2] = temp[i][2];
        }
    }
}
int miniSpanningTree(int n, int m, int** cost, int costRowLen,
                     int* costColLen ) {
    // write code here
    int column = costColLen[0] - 1; //数组下标2
    mergeSort(cost, 0, m - 1); //把他换成递归排序即可

    int arr[n + 1];
    for (int  i = 0; i <= n; i++) {
        arr[i] = i; //标记集合
    }

    int sum = 0;
    int count = 0;
    for (int i = 0; i < m; i++) {
        if (arr[cost[i][0]] != arr[cost[i][1]]) {
            sum += cost[i][column];
            count++;
            int  tmp  = arr[cost[i][1]];
            for (int k = 0; k < n + 1; k++) {
                if (arr[k] == tmp) {
                    arr[k] = arr[cost[i][0]];
                }
            }
        }
        if (count == n - 1 )  {
            return sum;
        }
    }
    return -1;

}