go最小生成树

package main

import (
	"fmt"
	"sort"
)

var (
	n, m  int //n为点数 m为边数
	edges []Edge
	pre   []int
)

// Edge 记录边
type Edge struct {
	from, to int
	val      int
}

type byVal []Edge

func (b byVal) Len() int {
	return len(b)
}

func (b byVal) Swap(i, j int) {
	b[i], b[j] = b[j], b[i]
}

func (b byVal) Less(i, j int) bool {
	return b[i].val < b[j].val
}

func find(x int) int {
	if pre[x] == x {
		return x
	} else {
		root := find(pre[x])
		pre[x] = root
		return pre[x]
	}
}

func main() {
	fmt.Scanf("%d %d", &n, &m)
	pre = make([]int, n)
	for i := 0; i < n; i++ {
		pre[i] = i
	}
	edges = make([]Edge, m)
	for i := 0; i < m; i++ {
		var a, b, c int
		fmt.Scanf("%d %d %d", &a, &b, &c)
		a--
		b--
		edges[i].from = a
		edges[i].to = b
		edges[i].val = c
	}
	sort.Sort(byVal(edges))
	//fmt.Println(edges)
	res := 0
	for i := 0; i < m; i++ {
		from := edges[i].from
		to := edges[i].to
		anFrom := find(from)
		anTo := find(to)
		if anFrom != anTo {
			res += edges[i].val
			pre[anTo] = anFrom
		}
	}
	an0 := find(0)
	for i := 1; i < n; i++ {
		if find(i) != an0 {
			res = -1
			break
		}
	}
	fmt.Println(res)
}

/*
4 3
1 2 1
1 3 10
2 3 3

5 6
1 2 3
2 1 5
1 3 2
4 2 6
4 5 1
5 3 2
*/

  

上一篇:Kruskal算法


下一篇:牛客多校6 c_Delete Edges(三个数,任意两数组合的情况只出现一次)