最小生成树

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 返回最小的花费代价使得这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 <stdio.h>
#include <stdlib.h>
#include <string.h>
void swap(int* x, int* y) {
    int z[3] = {0};
    memcpy(z, x, 3 * sizeof(int));
    memcpy(x, y, 3 * sizeof(int));
    memcpy(y, z, 3 * sizeof(int));
}

typedef struct _Range {
    int start, end;
} Range;

Range new_Range(int s, int e) {
    Range r;
    r.start = s;
    r.end = e;
    return r;
}

void quick_sort(int* arr[], const int len) {
    if (len <= 0)
        return; //避免len等于负值时错误
    //r[]模拟堆疊,p为数量,r[p++]为push,r[--p]为pop且取得元素
    Range r[len];
    int p = 0;
    r[p++] = new_Range(0, len - 1);
    while (p) {
        Range range = r[--p];
        if (range.start >= range.end)
            continue;
        int mid = arr[range.end][2];
        int left = range.start, right = range.end - 1;
        while (left < right) {
            while (arr[left][2] < mid && left < right)
                left++;
            while (arr[right][2] >= mid && left < right)
                right--;
            if(left<right){
                swap(arr[left], arr[right]);
                //加速设置，使代码尽快遍历完,否则超时
                left++;
                right--;
            }
        }
        if (arr[left][2] > arr[range.end][2])
            swap(arr[left], arr[range.end]);
        else
            left++;
        r[p++] = new_Range(range.start, left - 1);
        r[p++] = new_Range(left + 1, range.end);
    }
}

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
    int* parent = (int*)malloc((n+10) * sizeof(int));
    for (int i = 1; i <=n; i++) { //初始父亲设置为自己
        parent[i] = i;
    }
    quick_sort(cost, costRowLen);//按边递增排序

    int res = 0;
    for (int i = 0; i < costRowLen;
            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;
}