1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
| package searchandgraph
import "sort"
var p []int
func find(x int) int { if x != p[x] { p[x] = find(p[x]) } return p[x] }
func kruskal() int { sort.Slice(edges, func(i, j int) bool { return edges[i].w < edges[j].w })
for i := 1; i <= n; i++ { p[i] = i }
var res, cnt int for i := 0; i < m; i++ { a, b, w := edges[i].a, edges[i].b, edges[i].w
a, b = find(a), find(b) if a != b { p[a] = b res += w cnt++ } }
if cnt < n-1 { return INF }
return res }
|