1584.连接所有点的最小费用

最小生成树问题，Kruskal 算法

任意一颗最小生成树一定包含无向图中权值最小的边。

把任何一个生成森林扩展成最小生成树，一定使用了图中剩余边中权值最小的边。

证明方法： 树上加一条边成环 + 反证法

时间复杂度：O(N^2logN)
空间复杂度：O(N^2)

func minCostConnectPoints(points [][]int) int {
    n := len(points)
    groups := make([]int, n)
    edges := [][]int{}
    ans := 0

    // 并查集
    for i := 0; i < n; i++ {
        groups[i] = i
    }

    var find func(int) int
    find = func(i int) int {
        if i == groups[i] {
            return i
        }
        groups[i] = find(groups[i])
        return groups[i]
    }

    union := func(x, y int) {
        gx := find(x)
        gy := find(y)

        if gx != gy {
            groups[gx] = gy
        }
    }

    // 构建出边数组
    for i := 0; i < n; i ++ {
        for j := i + 1; j < n; j++ {
            xi := points[i][0]
            yi := points[i][1]
            xj := points[j][0]
            yj := points[j][1]

            edges = append(edges, []int{i, j, abs(xi-xj) + abs(yi-yj)})
        }
    }

    // 根据权重排序
    sort.Slice(edges, func(i, j int) bool {
        return edges[i][2] < edges[j][2]
    })
    
    // 依次链接，计算费用
    left := n - 1
    for _, edge := range edges {
        if left == 0 {
            break
        }
        if find(edge[0]) == find(edge[1]) {
            continue
        }else{
            union(edge[0], edge[1])
            ans += edge[2]
        }
        left--
    }

    return ans
}

func abs(val int) int {
    if val < 0 {
        return -val
    }
    return val
}