type Edge struct {
u, v, weight int
}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
func kruskal(n int, edges []Edge) int {
}type Edge struct {
u, v, weight int
}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
func kruskal(n int, edges []Edge) int {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
}type Edge struct {
u, v, weight int
}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
func kruskal(n int, edges []Edge) int {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
sort.Slice(edges, func(i, j int) bool {
return edges[i].weight < edges[j].weight
})
}type Edge struct {
u, v, weight int
}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
func kruskal(n int, edges []Edge) int {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
sort.Slice(edges, func(i, j int) bool {
return edges[i].weight < edges[j].weight
})
// We need to know when two nodes are already connected. Union-find handles
// that; start with every node in its own set (parent[i] = i).
}type Edge struct {
u, v, weight int
}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
func kruskal(n int, edges []Edge) int {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
sort.Slice(edges, func(i, j int) bool {
return edges[i].weight < edges[j].weight
})
// We need to know when two nodes are already connected. Union-find handles
// that; start with every node in its own set (parent[i] = i).
parent := make([]int, n)
for i := range parent {
parent[i] = i
}
}type Edge struct {
u, v, weight int
}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
func kruskal(n int, edges []Edge) int {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
sort.Slice(edges, func(i, j int) bool {
return edges[i].weight < edges[j].weight
})
// We need to know when two nodes are already connected. Union-find handles
// that; start with every node in its own set (parent[i] = i).
parent := make([]int, n)
for i := range parent {
parent[i] = i
}
// find returns the representative of x's set, compressing the path as it goes.
}type Edge struct {
u, v, weight int
}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
func kruskal(n int, edges []Edge) int {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
sort.Slice(edges, func(i, j int) bool {
return edges[i].weight < edges[j].weight
})
// We need to know when two nodes are already connected. Union-find handles
// that; start with every node in its own set (parent[i] = i).
parent := make([]int, n)
for i := range parent {
parent[i] = i
}
// find returns the representative of x's set, compressing the path as it goes.
var find func(x int) int
find = func(x int) int {
if parent[x] != x {
parent[x] = find(parent[x])
}
return parent[x]
}
}type Edge struct {
u, v, weight int
}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
func kruskal(n int, edges []Edge) int {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
sort.Slice(edges, func(i, j int) bool {
return edges[i].weight < edges[j].weight
})
// We need to know when two nodes are already connected. Union-find handles
// that; start with every node in its own set (parent[i] = i).
parent := make([]int, n)
for i := range parent {
parent[i] = i
}
// find returns the representative of x's set, compressing the path as it goes.
var find func(x int) int
find = func(x int) int {
if parent[x] != x {
parent[x] = find(parent[x])
}
return parent[x]
}
// total = summed weight of chosen edges; used = how many we've added so far.
}type Edge struct {
u, v, weight int
}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
func kruskal(n int, edges []Edge) int {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
sort.Slice(edges, func(i, j int) bool {
return edges[i].weight < edges[j].weight
})
// We need to know when two nodes are already connected. Union-find handles
// that; start with every node in its own set (parent[i] = i).
parent := make([]int, n)
for i := range parent {
parent[i] = i
}
// find returns the representative of x's set, compressing the path as it goes.
var find func(x int) int
find = func(x int) int {
if parent[x] != x {
parent[x] = find(parent[x])
}
return parent[x]
}
// total = summed weight of chosen edges; used = how many we've added so far.
total, used := 0, 0
}type Edge struct {
u, v, weight int
}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
func kruskal(n int, edges []Edge) int {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
sort.Slice(edges, func(i, j int) bool {
return edges[i].weight < edges[j].weight
})
// We need to know when two nodes are already connected. Union-find handles
// that; start with every node in its own set (parent[i] = i).
parent := make([]int, n)
for i := range parent {
parent[i] = i
}
// find returns the representative of x's set, compressing the path as it goes.
var find func(x int) int
find = func(x int) int {
if parent[x] != x {
parent[x] = find(parent[x])
}
return parent[x]
}
// total = summed weight of chosen edges; used = how many we've added so far.
total, used := 0, 0
// Which components do this edge's two endpoints currently belong to?
}type Edge struct {
u, v, weight int
}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
func kruskal(n int, edges []Edge) int {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
sort.Slice(edges, func(i, j int) bool {
return edges[i].weight < edges[j].weight
})
// We need to know when two nodes are already connected. Union-find handles
// that; start with every node in its own set (parent[i] = i).
parent := make([]int, n)
for i := range parent {
parent[i] = i
}
// find returns the representative of x's set, compressing the path as it goes.
var find func(x int) int
find = func(x int) int {
if parent[x] != x {
parent[x] = find(parent[x])
}
return parent[x]
}
// total = summed weight of chosen edges; used = how many we've added so far.
total, used := 0, 0
for _, e := range edges {
// Which components do this edge's two endpoints currently belong to?
ru, rv := find(e.u), find(e.v)
}
}type Edge struct {
u, v, weight int
}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
func kruskal(n int, edges []Edge) int {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
sort.Slice(edges, func(i, j int) bool {
return edges[i].weight < edges[j].weight
})
// We need to know when two nodes are already connected. Union-find handles
// that; start with every node in its own set (parent[i] = i).
parent := make([]int, n)
for i := range parent {
parent[i] = i
}
// find returns the representative of x's set, compressing the path as it goes.
var find func(x int) int
find = func(x int) int {
if parent[x] != x {
parent[x] = find(parent[x])
}
return parent[x]
}
// total = summed weight of chosen edges; used = how many we've added so far.
total, used := 0, 0
for _, e := range edges {
// Which components do this edge's two endpoints currently belong to?
ru, rv := find(e.u), find(e.v)
// Same component already? Adding this edge would close a cycle — skip it.
}
}type Edge struct {
u, v, weight int
}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
func kruskal(n int, edges []Edge) int {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
sort.Slice(edges, func(i, j int) bool {
return edges[i].weight < edges[j].weight
})
// We need to know when two nodes are already connected. Union-find handles
// that; start with every node in its own set (parent[i] = i).
parent := make([]int, n)
for i := range parent {
parent[i] = i
}
// find returns the representative of x's set, compressing the path as it goes.
var find func(x int) int
find = func(x int) int {
if parent[x] != x {
parent[x] = find(parent[x])
}
return parent[x]
}
// total = summed weight of chosen edges; used = how many we've added so far.
total, used := 0, 0
for _, e := range edges {
// Which components do this edge's two endpoints currently belong to?
ru, rv := find(e.u), find(e.v)
// Same component already? Adding this edge would close a cycle — skip it.
if ru == rv {
continue
}
}
}type Edge struct {
u, v, weight int
}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
func kruskal(n int, edges []Edge) int {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
sort.Slice(edges, func(i, j int) bool {
return edges[i].weight < edges[j].weight
})
// We need to know when two nodes are already connected. Union-find handles
// that; start with every node in its own set (parent[i] = i).
parent := make([]int, n)
for i := range parent {
parent[i] = i
}
// find returns the representative of x's set, compressing the path as it goes.
var find func(x int) int
find = func(x int) int {
if parent[x] != x {
parent[x] = find(parent[x])
}
return parent[x]
}
// total = summed weight of chosen edges; used = how many we've added so far.
total, used := 0, 0
for _, e := range edges {
// Which components do this edge's two endpoints currently belong to?
ru, rv := find(e.u), find(e.v)
// Same component already? Adding this edge would close a cycle — skip it.
if ru == rv {
continue
}
// Different components: keep the edge and merge the two sets into one.
}
}type Edge struct {
u, v, weight int
}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
func kruskal(n int, edges []Edge) int {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
sort.Slice(edges, func(i, j int) bool {
return edges[i].weight < edges[j].weight
})
// We need to know when two nodes are already connected. Union-find handles
// that; start with every node in its own set (parent[i] = i).
parent := make([]int, n)
for i := range parent {
parent[i] = i
}
// find returns the representative of x's set, compressing the path as it goes.
var find func(x int) int
find = func(x int) int {
if parent[x] != x {
parent[x] = find(parent[x])
}
return parent[x]
}
// total = summed weight of chosen edges; used = how many we've added so far.
total, used := 0, 0
for _, e := range edges {
// Which components do this edge's two endpoints currently belong to?
ru, rv := find(e.u), find(e.v)
// Same component already? Adding this edge would close a cycle — skip it.
if ru == rv {
continue
}
// Different components: keep the edge and merge the two sets into one.
parent[ru] = rv
total += e.weight
used++
}
}type Edge struct {
u, v, weight int
}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
func kruskal(n int, edges []Edge) int {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
sort.Slice(edges, func(i, j int) bool {
return edges[i].weight < edges[j].weight
})
// We need to know when two nodes are already connected. Union-find handles
// that; start with every node in its own set (parent[i] = i).
parent := make([]int, n)
for i := range parent {
parent[i] = i
}
// find returns the representative of x's set, compressing the path as it goes.
var find func(x int) int
find = func(x int) int {
if parent[x] != x {
parent[x] = find(parent[x])
}
return parent[x]
}
// total = summed weight of chosen edges; used = how many we've added so far.
total, used := 0, 0
for _, e := range edges {
// Which components do this edge's two endpoints currently belong to?
ru, rv := find(e.u), find(e.v)
// Same component already? Adding this edge would close a cycle — skip it.
if ru == rv {
continue
}
// Different components: keep the edge and merge the two sets into one.
parent[ru] = rv
total += e.weight
used++
// A spanning tree on n nodes has exactly n-1 edges; stop once it's full.
}
}type Edge struct {
u, v, weight int
}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
func kruskal(n int, edges []Edge) int {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
sort.Slice(edges, func(i, j int) bool {
return edges[i].weight < edges[j].weight
})
// We need to know when two nodes are already connected. Union-find handles
// that; start with every node in its own set (parent[i] = i).
parent := make([]int, n)
for i := range parent {
parent[i] = i
}
// find returns the representative of x's set, compressing the path as it goes.
var find func(x int) int
find = func(x int) int {
if parent[x] != x {
parent[x] = find(parent[x])
}
return parent[x]
}
// total = summed weight of chosen edges; used = how many we've added so far.
total, used := 0, 0
for _, e := range edges {
// Which components do this edge's two endpoints currently belong to?
ru, rv := find(e.u), find(e.v)
// Same component already? Adding this edge would close a cycle — skip it.
if ru == rv {
continue
}
// Different components: keep the edge and merge the two sets into one.
parent[ru] = rv
total += e.weight
used++
// A spanning tree on n nodes has exactly n-1 edges; stop once it's full.
if used == n-1 {
break
}
}
return total // O(E log E), dominated by the sort
}Tap the left half to go back, the right half to go forward.
Arrow keys or space to navigate · Esc to exit.