020 最小生成树

var arr []int
const MAXM = 200001
var edges [][3]int = make([][3]int, MAXM)

func find(i int) int {
    if arr[i] != i {
        arr[i] = find(arr[i])
    }
    return arr[i]
}

func union(x, y int) {
    arr[find(x)] = arr[find(y)]
}

func isSameSet(a, b int) bool {
    return find(a) == find(b)
}

func main() {
    slices.SortFunc(edges, func(a, b [3]int) int {
        return a[2] - b[2]
    })
    arr = make([]int, n+1)
    for i := range arr {
        arr[i] = i
    }
    ans := 0
    for _, edge := range edges {
        if !isSameSet(edge[0], edge[1]) {
            union(edge[0], edge[1])
            ans += edge[2]
        }
    }
}