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
}# Each edge is a (u, v, weight) tuple.
# kruskal returns the total weight of a minimum spanning tree over n nodes.
def kruskal(n, edges):
pass# Each edge is a (u, v, weight) tuple.
# kruskal returns the total weight of a minimum spanning tree over n nodes.
def kruskal(n, edges):
# Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
# graph acyclic. So examine edges from lightest to heaviest.
pass# Each edge is a (u, v, weight) tuple.
# kruskal returns the total weight of a minimum spanning tree over n nodes.
def kruskal(n, edges):
# Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
# graph acyclic. So examine edges from lightest to heaviest.
edges.sort(key=lambda e: e[2])# Each edge is a (u, v, weight) tuple.
# kruskal returns the total weight of a minimum spanning tree over n nodes.
def kruskal(n, edges):
# Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
# graph acyclic. So examine edges from lightest to heaviest.
edges.sort(key=lambda e: e[2])
# 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).# Each edge is a (u, v, weight) tuple.
# kruskal returns the total weight of a minimum spanning tree over n nodes.
def kruskal(n, edges):
# Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
# graph acyclic. So examine edges from lightest to heaviest.
edges.sort(key=lambda e: e[2])
# 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 = list(range(n))# Each edge is a (u, v, weight) tuple.
# kruskal returns the total weight of a minimum spanning tree over n nodes.
def kruskal(n, edges):
# Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
# graph acyclic. So examine edges from lightest to heaviest.
edges.sort(key=lambda e: e[2])
# 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 = list(range(n))
# find returns the representative of x's set, compressing the path as it goes.# Each edge is a (u, v, weight) tuple.
# kruskal returns the total weight of a minimum spanning tree over n nodes.
def kruskal(n, edges):
# Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
# graph acyclic. So examine edges from lightest to heaviest.
edges.sort(key=lambda e: e[2])
# 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 = list(range(n))
# find returns the representative of x's set, compressing the path as it goes.
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]# Each edge is a (u, v, weight) tuple.
# kruskal returns the total weight of a minimum spanning tree over n nodes.
def kruskal(n, edges):
# Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
# graph acyclic. So examine edges from lightest to heaviest.
edges.sort(key=lambda e: e[2])
# 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 = list(range(n))
# find returns the representative of x's set, compressing the path as it goes.
def find(x):
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.# Each edge is a (u, v, weight) tuple.
# kruskal returns the total weight of a minimum spanning tree over n nodes.
def kruskal(n, edges):
# Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
# graph acyclic. So examine edges from lightest to heaviest.
edges.sort(key=lambda e: e[2])
# 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 = list(range(n))
# find returns the representative of x's set, compressing the path as it goes.
def find(x):
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# Each edge is a (u, v, weight) tuple.
# kruskal returns the total weight of a minimum spanning tree over n nodes.
def kruskal(n, edges):
# Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
# graph acyclic. So examine edges from lightest to heaviest.
edges.sort(key=lambda e: e[2])
# 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 = list(range(n))
# find returns the representative of x's set, compressing the path as it goes.
def find(x):
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?# Each edge is a (u, v, weight) tuple.
# kruskal returns the total weight of a minimum spanning tree over n nodes.
def kruskal(n, edges):
# Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
# graph acyclic. So examine edges from lightest to heaviest.
edges.sort(key=lambda e: e[2])
# 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 = list(range(n))
# find returns the representative of x's set, compressing the path as it goes.
def find(x):
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 u, v, weight in edges:
# Which components do this edge's two endpoints currently belong to?
ru, rv = find(u), find(v)# Each edge is a (u, v, weight) tuple.
# kruskal returns the total weight of a minimum spanning tree over n nodes.
def kruskal(n, edges):
# Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
# graph acyclic. So examine edges from lightest to heaviest.
edges.sort(key=lambda e: e[2])
# 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 = list(range(n))
# find returns the representative of x's set, compressing the path as it goes.
def find(x):
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 u, v, weight in edges:
# Which components do this edge's two endpoints currently belong to?
ru, rv = find(u), find(v)
# Same component already? Adding this edge would close a cycle — skip it.# Each edge is a (u, v, weight) tuple.
# kruskal returns the total weight of a minimum spanning tree over n nodes.
def kruskal(n, edges):
# Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
# graph acyclic. So examine edges from lightest to heaviest.
edges.sort(key=lambda e: e[2])
# 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 = list(range(n))
# find returns the representative of x's set, compressing the path as it goes.
def find(x):
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 u, v, weight in edges:
# Which components do this edge's two endpoints currently belong to?
ru, rv = find(u), find(v)
# Same component already? Adding this edge would close a cycle — skip it.
if ru == rv:
continue# Each edge is a (u, v, weight) tuple.
# kruskal returns the total weight of a minimum spanning tree over n nodes.
def kruskal(n, edges):
# Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
# graph acyclic. So examine edges from lightest to heaviest.
edges.sort(key=lambda e: e[2])
# 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 = list(range(n))
# find returns the representative of x's set, compressing the path as it goes.
def find(x):
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 u, v, weight in edges:
# Which components do this edge's two endpoints currently belong to?
ru, rv = find(u), find(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.# Each edge is a (u, v, weight) tuple.
# kruskal returns the total weight of a minimum spanning tree over n nodes.
def kruskal(n, edges):
# Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
# graph acyclic. So examine edges from lightest to heaviest.
edges.sort(key=lambda e: e[2])
# 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 = list(range(n))
# find returns the representative of x's set, compressing the path as it goes.
def find(x):
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 u, v, weight in edges:
# Which components do this edge's two endpoints currently belong to?
ru, rv = find(u), find(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 += weight
used += 1# Each edge is a (u, v, weight) tuple.
# kruskal returns the total weight of a minimum spanning tree over n nodes.
def kruskal(n, edges):
# Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
# graph acyclic. So examine edges from lightest to heaviest.
edges.sort(key=lambda e: e[2])
# 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 = list(range(n))
# find returns the representative of x's set, compressing the path as it goes.
def find(x):
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 u, v, weight in edges:
# Which components do this edge's two endpoints currently belong to?
ru, rv = find(u), find(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 += weight
used += 1
# A spanning tree on n nodes has exactly n-1 edges; stop once it's full.# Each edge is a (u, v, weight) tuple.
# kruskal returns the total weight of a minimum spanning tree over n nodes.
def kruskal(n, edges):
# Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
# graph acyclic. So examine edges from lightest to heaviest.
edges.sort(key=lambda e: e[2])
# 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 = list(range(n))
# find returns the representative of x's set, compressing the path as it goes.
def find(x):
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 u, v, weight in edges:
# Which components do this edge's two endpoints currently belong to?
ru, rv = find(u), find(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 += weight
used += 1
# 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// Each edge is an object { u, v, weight }.
// kruskal returns the total weight of a minimum spanning tree over n nodes.
function kruskal(n, edges) {
}// Each edge is an object { u, v, weight }.
// kruskal returns the total weight of a minimum spanning tree over n nodes.
function kruskal(n, edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
}// Each edge is an object { u, v, weight }.
// kruskal returns the total weight of a minimum spanning tree over n nodes.
function kruskal(n, edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
edges.sort((a, b) => a.weight - b.weight);
}// Each edge is an object { u, v, weight }.
// kruskal returns the total weight of a minimum spanning tree over n nodes.
function kruskal(n, edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
edges.sort((a, b) => a.weight - b.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).
}// Each edge is an object { u, v, weight }.
// kruskal returns the total weight of a minimum spanning tree over n nodes.
function kruskal(n, edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
edges.sort((a, b) => a.weight - b.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).
const parent = new Array(n);
for (let i = 0; i < n; i++) {
parent[i] = i;
}
}// Each edge is an object { u, v, weight }.
// kruskal returns the total weight of a minimum spanning tree over n nodes.
function kruskal(n, edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
edges.sort((a, b) => a.weight - b.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).
const parent = new Array(n);
for (let i = 0; i < n; i++) {
parent[i] = i;
}
// find returns the representative of x's set, compressing the path as it goes.
}// Each edge is an object { u, v, weight }.
// kruskal returns the total weight of a minimum spanning tree over n nodes.
function kruskal(n, edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
edges.sort((a, b) => a.weight - b.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).
const parent = new Array(n);
for (let i = 0; i < n; i++) {
parent[i] = i;
}
// find returns the representative of x's set, compressing the path as it goes.
function find(x) {
if (parent[x] !== x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
}// Each edge is an object { u, v, weight }.
// kruskal returns the total weight of a minimum spanning tree over n nodes.
function kruskal(n, edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
edges.sort((a, b) => a.weight - b.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).
const parent = new Array(n);
for (let i = 0; i < n; i++) {
parent[i] = i;
}
// find returns the representative of x's set, compressing the path as it goes.
function find(x) {
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.
}// Each edge is an object { u, v, weight }.
// kruskal returns the total weight of a minimum spanning tree over n nodes.
function kruskal(n, edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
edges.sort((a, b) => a.weight - b.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).
const parent = new Array(n);
for (let i = 0; i < n; i++) {
parent[i] = i;
}
// find returns the representative of x's set, compressing the path as it goes.
function find(x) {
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.
let total = 0, used = 0;
}// Each edge is an object { u, v, weight }.
// kruskal returns the total weight of a minimum spanning tree over n nodes.
function kruskal(n, edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
edges.sort((a, b) => a.weight - b.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).
const parent = new Array(n);
for (let i = 0; i < n; i++) {
parent[i] = i;
}
// find returns the representative of x's set, compressing the path as it goes.
function find(x) {
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.
let total = 0, used = 0;
// Which components do this edge's two endpoints currently belong to?
}// Each edge is an object { u, v, weight }.
// kruskal returns the total weight of a minimum spanning tree over n nodes.
function kruskal(n, edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
edges.sort((a, b) => a.weight - b.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).
const parent = new Array(n);
for (let i = 0; i < n; i++) {
parent[i] = i;
}
// find returns the representative of x's set, compressing the path as it goes.
function find(x) {
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.
let total = 0, used = 0;
for (const e of edges) {
// Which components do this edge's two endpoints currently belong to?
const ru = find(e.u), rv = find(e.v);
}
}// Each edge is an object { u, v, weight }.
// kruskal returns the total weight of a minimum spanning tree over n nodes.
function kruskal(n, edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
edges.sort((a, b) => a.weight - b.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).
const parent = new Array(n);
for (let i = 0; i < n; i++) {
parent[i] = i;
}
// find returns the representative of x's set, compressing the path as it goes.
function find(x) {
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.
let total = 0, used = 0;
for (const e of edges) {
// Which components do this edge's two endpoints currently belong to?
const ru = find(e.u), rv = find(e.v);
// Same component already? Adding this edge would close a cycle — skip it.
}
}// Each edge is an object { u, v, weight }.
// kruskal returns the total weight of a minimum spanning tree over n nodes.
function kruskal(n, edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
edges.sort((a, b) => a.weight - b.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).
const parent = new Array(n);
for (let i = 0; i < n; i++) {
parent[i] = i;
}
// find returns the representative of x's set, compressing the path as it goes.
function find(x) {
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.
let total = 0, used = 0;
for (const e of edges) {
// Which components do this edge's two endpoints currently belong to?
const ru = find(e.u), rv = find(e.v);
// Same component already? Adding this edge would close a cycle — skip it.
if (ru === rv) {
continue;
}
}
}// Each edge is an object { u, v, weight }.
// kruskal returns the total weight of a minimum spanning tree over n nodes.
function kruskal(n, edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
edges.sort((a, b) => a.weight - b.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).
const parent = new Array(n);
for (let i = 0; i < n; i++) {
parent[i] = i;
}
// find returns the representative of x's set, compressing the path as it goes.
function find(x) {
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.
let total = 0, used = 0;
for (const e of edges) {
// Which components do this edge's two endpoints currently belong to?
const ru = find(e.u), rv = 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.
}
}// Each edge is an object { u, v, weight }.
// kruskal returns the total weight of a minimum spanning tree over n nodes.
function kruskal(n, edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
edges.sort((a, b) => a.weight - b.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).
const parent = new Array(n);
for (let i = 0; i < n; i++) {
parent[i] = i;
}
// find returns the representative of x's set, compressing the path as it goes.
function find(x) {
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.
let total = 0, used = 0;
for (const e of edges) {
// Which components do this edge's two endpoints currently belong to?
const ru = find(e.u), rv = 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++;
}
}// Each edge is an object { u, v, weight }.
// kruskal returns the total weight of a minimum spanning tree over n nodes.
function kruskal(n, edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
edges.sort((a, b) => a.weight - b.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).
const parent = new Array(n);
for (let i = 0; i < n; i++) {
parent[i] = i;
}
// find returns the representative of x's set, compressing the path as it goes.
function find(x) {
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.
let total = 0, used = 0;
for (const e of edges) {
// Which components do this edge's two endpoints currently belong to?
const ru = find(e.u), rv = 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.
}
}// Each edge is an object { u, v, weight }.
// kruskal returns the total weight of a minimum spanning tree over n nodes.
function kruskal(n, edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
edges.sort((a, b) => a.weight - b.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).
const parent = new Array(n);
for (let i = 0; i < n; i++) {
parent[i] = i;
}
// find returns the representative of x's set, compressing the path as it goes.
function find(x) {
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.
let total = 0, used = 0;
for (const e of edges) {
// Which components do this edge's two endpoints currently belong to?
const ru = find(e.u), rv = 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
}interface Edge {
u: number;
v: number;
weight: number;
}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
function kruskal(n: number, edges: Edge[]): number {
}interface Edge {
u: number;
v: number;
weight: number;
}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
function kruskal(n: number, edges: Edge[]): number {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
}interface Edge {
u: number;
v: number;
weight: number;
}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
function kruskal(n: number, edges: Edge[]): number {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
edges.sort((a, b) => a.weight - b.weight);
}interface Edge {
u: number;
v: number;
weight: number;
}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
function kruskal(n: number, edges: Edge[]): number {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
edges.sort((a, b) => a.weight - b.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).
}interface Edge {
u: number;
v: number;
weight: number;
}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
function kruskal(n: number, edges: Edge[]): number {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
edges.sort((a, b) => a.weight - b.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).
const parent: number[] = new Array(n);
for (let i = 0; i < n; i++) {
parent[i] = i;
}
}interface Edge {
u: number;
v: number;
weight: number;
}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
function kruskal(n: number, edges: Edge[]): number {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
edges.sort((a, b) => a.weight - b.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).
const parent: number[] = new Array(n);
for (let i = 0; i < n; i++) {
parent[i] = i;
}
// find returns the representative of x's set, compressing the path as it goes.
}interface Edge {
u: number;
v: number;
weight: number;
}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
function kruskal(n: number, edges: Edge[]): number {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
edges.sort((a, b) => a.weight - b.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).
const parent: number[] = new Array(n);
for (let i = 0; i < n; i++) {
parent[i] = i;
}
// find returns the representative of x's set, compressing the path as it goes.
function find(x: number): number {
if (parent[x] !== x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
}interface Edge {
u: number;
v: number;
weight: number;
}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
function kruskal(n: number, edges: Edge[]): number {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
edges.sort((a, b) => a.weight - b.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).
const parent: number[] = new Array(n);
for (let i = 0; i < n; i++) {
parent[i] = i;
}
// find returns the representative of x's set, compressing the path as it goes.
function find(x: number): number {
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.
}interface Edge {
u: number;
v: number;
weight: number;
}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
function kruskal(n: number, edges: Edge[]): number {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
edges.sort((a, b) => a.weight - b.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).
const parent: number[] = new Array(n);
for (let i = 0; i < n; i++) {
parent[i] = i;
}
// find returns the representative of x's set, compressing the path as it goes.
function find(x: number): number {
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.
let total = 0, used = 0;
}interface Edge {
u: number;
v: number;
weight: number;
}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
function kruskal(n: number, edges: Edge[]): number {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
edges.sort((a, b) => a.weight - b.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).
const parent: number[] = new Array(n);
for (let i = 0; i < n; i++) {
parent[i] = i;
}
// find returns the representative of x's set, compressing the path as it goes.
function find(x: number): number {
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.
let total = 0, used = 0;
// Which components do this edge's two endpoints currently belong to?
}interface Edge {
u: number;
v: number;
weight: number;
}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
function kruskal(n: number, edges: Edge[]): number {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
edges.sort((a, b) => a.weight - b.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).
const parent: number[] = new Array(n);
for (let i = 0; i < n; i++) {
parent[i] = i;
}
// find returns the representative of x's set, compressing the path as it goes.
function find(x: number): number {
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.
let total = 0, used = 0;
for (const e of edges) {
// Which components do this edge's two endpoints currently belong to?
const ru = find(e.u), rv = find(e.v);
}
}interface Edge {
u: number;
v: number;
weight: number;
}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
function kruskal(n: number, edges: Edge[]): number {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
edges.sort((a, b) => a.weight - b.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).
const parent: number[] = new Array(n);
for (let i = 0; i < n; i++) {
parent[i] = i;
}
// find returns the representative of x's set, compressing the path as it goes.
function find(x: number): number {
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.
let total = 0, used = 0;
for (const e of edges) {
// Which components do this edge's two endpoints currently belong to?
const ru = find(e.u), rv = find(e.v);
// Same component already? Adding this edge would close a cycle — skip it.
}
}interface Edge {
u: number;
v: number;
weight: number;
}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
function kruskal(n: number, edges: Edge[]): number {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
edges.sort((a, b) => a.weight - b.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).
const parent: number[] = new Array(n);
for (let i = 0; i < n; i++) {
parent[i] = i;
}
// find returns the representative of x's set, compressing the path as it goes.
function find(x: number): number {
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.
let total = 0, used = 0;
for (const e of edges) {
// Which components do this edge's two endpoints currently belong to?
const ru = find(e.u), rv = find(e.v);
// Same component already? Adding this edge would close a cycle — skip it.
if (ru === rv) {
continue;
}
}
}interface Edge {
u: number;
v: number;
weight: number;
}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
function kruskal(n: number, edges: Edge[]): number {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
edges.sort((a, b) => a.weight - b.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).
const parent: number[] = new Array(n);
for (let i = 0; i < n; i++) {
parent[i] = i;
}
// find returns the representative of x's set, compressing the path as it goes.
function find(x: number): number {
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.
let total = 0, used = 0;
for (const e of edges) {
// Which components do this edge's two endpoints currently belong to?
const ru = find(e.u), rv = 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.
}
}interface Edge {
u: number;
v: number;
weight: number;
}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
function kruskal(n: number, edges: Edge[]): number {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
edges.sort((a, b) => a.weight - b.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).
const parent: number[] = new Array(n);
for (let i = 0; i < n; i++) {
parent[i] = i;
}
// find returns the representative of x's set, compressing the path as it goes.
function find(x: number): number {
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.
let total = 0, used = 0;
for (const e of edges) {
// Which components do this edge's two endpoints currently belong to?
const ru = find(e.u), rv = 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++;
}
}interface Edge {
u: number;
v: number;
weight: number;
}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
function kruskal(n: number, edges: Edge[]): number {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
edges.sort((a, b) => a.weight - b.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).
const parent: number[] = new Array(n);
for (let i = 0; i < n; i++) {
parent[i] = i;
}
// find returns the representative of x's set, compressing the path as it goes.
function find(x: number): number {
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.
let total = 0, used = 0;
for (const e of edges) {
// Which components do this edge's two endpoints currently belong to?
const ru = find(e.u), rv = 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.
}
}interface Edge {
u: number;
v: number;
weight: number;
}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
function kruskal(n: number, edges: Edge[]): number {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
edges.sort((a, b) => a.weight - b.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).
const parent: number[] = new Array(n);
for (let i = 0; i < n; i++) {
parent[i] = i;
}
// find returns the representative of x's set, compressing the path as it goes.
function find(x: number): number {
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.
let total = 0, used = 0;
for (const e of edges) {
// Which components do this edge's two endpoints currently belong to?
const ru = find(e.u), rv = 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
}import java.util.Arrays;
class Solution {
record Edge(int u, int v, int weight) {}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
public int kruskal(int n, Edge[] edges) {
}
}import java.util.Arrays;
class Solution {
record Edge(int u, int v, int weight) {}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
public int kruskal(int n, Edge[] edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
}
}import java.util.Arrays;
class Solution {
record Edge(int u, int v, int weight) {}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
public int kruskal(int n, Edge[] edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
Arrays.sort(edges, (a, b) -> Integer.compare(a.weight(), b.weight()));
}
}import java.util.Arrays;
class Solution {
record Edge(int u, int v, int weight) {}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
public int kruskal(int n, Edge[] edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
Arrays.sort(edges, (a, b) -> Integer.compare(a.weight(), b.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).
}
}import java.util.Arrays;
class Solution {
record Edge(int u, int v, int weight) {}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
public int kruskal(int n, Edge[] edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
Arrays.sort(edges, (a, b) -> Integer.compare(a.weight(), b.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).
int[] parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
}import java.util.Arrays;
class Solution {
record Edge(int u, int v, int weight) {}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
public int kruskal(int n, Edge[] edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
Arrays.sort(edges, (a, b) -> Integer.compare(a.weight(), b.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).
int[] parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
// find returns the representative of x's set, compressing the path as it goes.
}import java.util.Arrays;
class Solution {
record Edge(int u, int v, int weight) {}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
public int kruskal(int n, Edge[] edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
Arrays.sort(edges, (a, b) -> Integer.compare(a.weight(), b.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).
int[] parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
// find returns the representative of x's set, compressing the path as it goes.
private int find(int[] parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}
}import java.util.Arrays;
class Solution {
record Edge(int u, int v, int weight) {}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
public int kruskal(int n, Edge[] edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
Arrays.sort(edges, (a, b) -> Integer.compare(a.weight(), b.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).
int[] parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// total = summed weight of chosen edges; used = how many we've added so far.
}
// find returns the representative of x's set, compressing the path as it goes.
private int find(int[] parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}
}import java.util.Arrays;
class Solution {
record Edge(int u, int v, int weight) {}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
public int kruskal(int n, Edge[] edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
Arrays.sort(edges, (a, b) -> Integer.compare(a.weight(), b.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).
int[] parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// total = summed weight of chosen edges; used = how many we've added so far.
int total = 0, used = 0;
}
// find returns the representative of x's set, compressing the path as it goes.
private int find(int[] parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}
}import java.util.Arrays;
class Solution {
record Edge(int u, int v, int weight) {}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
public int kruskal(int n, Edge[] edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
Arrays.sort(edges, (a, b) -> Integer.compare(a.weight(), b.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).
int[] parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// total = summed weight of chosen edges; used = how many we've added so far.
int total = 0, used = 0;
// Which components do this edge's two endpoints currently belong to?
}
// find returns the representative of x's set, compressing the path as it goes.
private int find(int[] parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}
}import java.util.Arrays;
class Solution {
record Edge(int u, int v, int weight) {}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
public int kruskal(int n, Edge[] edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
Arrays.sort(edges, (a, b) -> Integer.compare(a.weight(), b.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).
int[] parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// total = summed weight of chosen edges; used = how many we've added so far.
int total = 0, used = 0;
for (Edge e : edges) {
// Which components do this edge's two endpoints currently belong to?
int ru = find(parent, e.u()), rv = find(parent, e.v());
}
}
// find returns the representative of x's set, compressing the path as it goes.
private int find(int[] parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}
}import java.util.Arrays;
class Solution {
record Edge(int u, int v, int weight) {}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
public int kruskal(int n, Edge[] edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
Arrays.sort(edges, (a, b) -> Integer.compare(a.weight(), b.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).
int[] parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// total = summed weight of chosen edges; used = how many we've added so far.
int total = 0, used = 0;
for (Edge e : edges) {
// Which components do this edge's two endpoints currently belong to?
int ru = find(parent, e.u()), rv = find(parent, e.v());
// Same component already? Adding this edge would close a cycle — skip it.
}
}
// find returns the representative of x's set, compressing the path as it goes.
private int find(int[] parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}
}import java.util.Arrays;
class Solution {
record Edge(int u, int v, int weight) {}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
public int kruskal(int n, Edge[] edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
Arrays.sort(edges, (a, b) -> Integer.compare(a.weight(), b.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).
int[] parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// total = summed weight of chosen edges; used = how many we've added so far.
int total = 0, used = 0;
for (Edge e : edges) {
// Which components do this edge's two endpoints currently belong to?
int ru = find(parent, e.u()), rv = find(parent, e.v());
// Same component already? Adding this edge would close a cycle — skip it.
if (ru == rv) {
continue;
}
}
}
// find returns the representative of x's set, compressing the path as it goes.
private int find(int[] parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}
}import java.util.Arrays;
class Solution {
record Edge(int u, int v, int weight) {}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
public int kruskal(int n, Edge[] edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
Arrays.sort(edges, (a, b) -> Integer.compare(a.weight(), b.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).
int[] parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// total = summed weight of chosen edges; used = how many we've added so far.
int total = 0, used = 0;
for (Edge e : edges) {
// Which components do this edge's two endpoints currently belong to?
int ru = find(parent, e.u()), rv = find(parent, 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.
}
}
// find returns the representative of x's set, compressing the path as it goes.
private int find(int[] parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}
}import java.util.Arrays;
class Solution {
record Edge(int u, int v, int weight) {}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
public int kruskal(int n, Edge[] edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
Arrays.sort(edges, (a, b) -> Integer.compare(a.weight(), b.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).
int[] parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// total = summed weight of chosen edges; used = how many we've added so far.
int total = 0, used = 0;
for (Edge e : edges) {
// Which components do this edge's two endpoints currently belong to?
int ru = find(parent, e.u()), rv = find(parent, 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++;
}
}
// find returns the representative of x's set, compressing the path as it goes.
private int find(int[] parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}
}import java.util.Arrays;
class Solution {
record Edge(int u, int v, int weight) {}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
public int kruskal(int n, Edge[] edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
Arrays.sort(edges, (a, b) -> Integer.compare(a.weight(), b.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).
int[] parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// total = summed weight of chosen edges; used = how many we've added so far.
int total = 0, used = 0;
for (Edge e : edges) {
// Which components do this edge's two endpoints currently belong to?
int ru = find(parent, e.u()), rv = find(parent, 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.
}
}
// find returns the representative of x's set, compressing the path as it goes.
private int find(int[] parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}
}import java.util.Arrays;
class Solution {
record Edge(int u, int v, int weight) {}
// kruskal returns the total weight of a minimum spanning tree over n nodes.
public int kruskal(int n, Edge[] edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
Arrays.sort(edges, (a, b) -> Integer.compare(a.weight(), b.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).
int[] parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// total = summed weight of chosen edges; used = how many we've added so far.
int total = 0, used = 0;
for (Edge e : edges) {
// Which components do this edge's two endpoints currently belong to?
int ru = find(parent, e.u()), rv = find(parent, 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
}
// find returns the representative of x's set, compressing the path as it goes.
private int find(int[] parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}
}using System;
public class Solution {
public record Edge(int U, int V, int Weight);
// Kruskal returns the total weight of a minimum spanning tree over n nodes.
public int Kruskal(int n, Edge[] edges) {
}
}using System;
public class Solution {
public record Edge(int U, int V, int Weight);
// Kruskal returns the total weight of a minimum spanning tree over n nodes.
public int Kruskal(int n, Edge[] edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
}
}using System;
public class Solution {
public record Edge(int U, int V, int Weight);
// Kruskal returns the total weight of a minimum spanning tree over n nodes.
public int Kruskal(int n, Edge[] edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
Array.Sort(edges, (a, b) => a.Weight.CompareTo(b.Weight));
}
}using System;
public class Solution {
public record Edge(int U, int V, int Weight);
// Kruskal returns the total weight of a minimum spanning tree over n nodes.
public int Kruskal(int n, Edge[] edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
Array.Sort(edges, (a, b) => a.Weight.CompareTo(b.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).
}
}using System;
public class Solution {
public record Edge(int U, int V, int Weight);
// Kruskal returns the total weight of a minimum spanning tree over n nodes.
public int Kruskal(int n, Edge[] edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
Array.Sort(edges, (a, b) => a.Weight.CompareTo(b.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).
int[] parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
}using System;
public class Solution {
public record Edge(int U, int V, int Weight);
// Kruskal returns the total weight of a minimum spanning tree over n nodes.
public int Kruskal(int n, Edge[] edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
Array.Sort(edges, (a, b) => a.Weight.CompareTo(b.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).
int[] parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// Find returns the representative of x's set, compressing the path as it goes.
}
}using System;
public class Solution {
public record Edge(int U, int V, int Weight);
// Kruskal returns the total weight of a minimum spanning tree over n nodes.
public int Kruskal(int n, Edge[] edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
Array.Sort(edges, (a, b) => a.Weight.CompareTo(b.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).
int[] parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// Find returns the representative of x's set, compressing the path as it goes.
int Find(int x) {
if (parent[x] != x) {
parent[x] = Find(parent[x]);
}
return parent[x];
}
}
}using System;
public class Solution {
public record Edge(int U, int V, int Weight);
// Kruskal returns the total weight of a minimum spanning tree over n nodes.
public int Kruskal(int n, Edge[] edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
Array.Sort(edges, (a, b) => a.Weight.CompareTo(b.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).
int[] parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// Find returns the representative of x's set, compressing the path as it goes.
int Find(int x) {
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.
}
}using System;
public class Solution {
public record Edge(int U, int V, int Weight);
// Kruskal returns the total weight of a minimum spanning tree over n nodes.
public int Kruskal(int n, Edge[] edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
Array.Sort(edges, (a, b) => a.Weight.CompareTo(b.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).
int[] parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// Find returns the representative of x's set, compressing the path as it goes.
int Find(int x) {
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.
int total = 0, used = 0;
}
}using System;
public class Solution {
public record Edge(int U, int V, int Weight);
// Kruskal returns the total weight of a minimum spanning tree over n nodes.
public int Kruskal(int n, Edge[] edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
Array.Sort(edges, (a, b) => a.Weight.CompareTo(b.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).
int[] parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// Find returns the representative of x's set, compressing the path as it goes.
int Find(int x) {
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.
int total = 0, used = 0;
// Which components do this edge's two endpoints currently belong to?
}
}using System;
public class Solution {
public record Edge(int U, int V, int Weight);
// Kruskal returns the total weight of a minimum spanning tree over n nodes.
public int Kruskal(int n, Edge[] edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
Array.Sort(edges, (a, b) => a.Weight.CompareTo(b.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).
int[] parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// Find returns the representative of x's set, compressing the path as it goes.
int Find(int x) {
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.
int total = 0, used = 0;
foreach (Edge e in edges) {
// Which components do this edge's two endpoints currently belong to?
int ru = Find(e.U), rv = Find(e.V);
}
}
}using System;
public class Solution {
public record Edge(int U, int V, int Weight);
// Kruskal returns the total weight of a minimum spanning tree over n nodes.
public int Kruskal(int n, Edge[] edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
Array.Sort(edges, (a, b) => a.Weight.CompareTo(b.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).
int[] parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// Find returns the representative of x's set, compressing the path as it goes.
int Find(int x) {
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.
int total = 0, used = 0;
foreach (Edge e in edges) {
// Which components do this edge's two endpoints currently belong to?
int ru = Find(e.U), rv = Find(e.V);
// Same component already? Adding this edge would close a cycle — skip it.
}
}
}using System;
public class Solution {
public record Edge(int U, int V, int Weight);
// Kruskal returns the total weight of a minimum spanning tree over n nodes.
public int Kruskal(int n, Edge[] edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
Array.Sort(edges, (a, b) => a.Weight.CompareTo(b.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).
int[] parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// Find returns the representative of x's set, compressing the path as it goes.
int Find(int x) {
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.
int total = 0, used = 0;
foreach (Edge e in edges) {
// Which components do this edge's two endpoints currently belong to?
int ru = Find(e.U), rv = Find(e.V);
// Same component already? Adding this edge would close a cycle — skip it.
if (ru == rv) {
continue;
}
}
}
}using System;
public class Solution {
public record Edge(int U, int V, int Weight);
// Kruskal returns the total weight of a minimum spanning tree over n nodes.
public int Kruskal(int n, Edge[] edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
Array.Sort(edges, (a, b) => a.Weight.CompareTo(b.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).
int[] parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// Find returns the representative of x's set, compressing the path as it goes.
int Find(int x) {
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.
int total = 0, used = 0;
foreach (Edge e in edges) {
// Which components do this edge's two endpoints currently belong to?
int ru = Find(e.U), rv = 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.
}
}
}using System;
public class Solution {
public record Edge(int U, int V, int Weight);
// Kruskal returns the total weight of a minimum spanning tree over n nodes.
public int Kruskal(int n, Edge[] edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
Array.Sort(edges, (a, b) => a.Weight.CompareTo(b.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).
int[] parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// Find returns the representative of x's set, compressing the path as it goes.
int Find(int x) {
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.
int total = 0, used = 0;
foreach (Edge e in edges) {
// Which components do this edge's two endpoints currently belong to?
int ru = Find(e.U), rv = 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++;
}
}
}using System;
public class Solution {
public record Edge(int U, int V, int Weight);
// Kruskal returns the total weight of a minimum spanning tree over n nodes.
public int Kruskal(int n, Edge[] edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
Array.Sort(edges, (a, b) => a.Weight.CompareTo(b.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).
int[] parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// Find returns the representative of x's set, compressing the path as it goes.
int Find(int x) {
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.
int total = 0, used = 0;
foreach (Edge e in edges) {
// Which components do this edge's two endpoints currently belong to?
int ru = Find(e.U), rv = 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.
}
}
}using System;
public class Solution {
public record Edge(int U, int V, int Weight);
// Kruskal returns the total weight of a minimum spanning tree over n nodes.
public int Kruskal(int n, Edge[] edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
Array.Sort(edges, (a, b) => a.Weight.CompareTo(b.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).
int[] parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// Find returns the representative of x's set, compressing the path as it goes.
int Find(int x) {
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.
int total = 0, used = 0;
foreach (Edge e in edges) {
// Which components do this edge's two endpoints currently belong to?
int ru = Find(e.U), rv = 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
}
}#include <stdlib.h>
typedef struct {
int u, v, weight;
} Edge;
// Declared up front so kruskal can call it before it is defined further down.
static int find(int* parent, int x);
// kruskal returns the total weight of a minimum spanning tree over n nodes.
int kruskal(int n, Edge* edges, int edgesSize) {
}#include <stdlib.h>
typedef struct {
int u, v, weight;
} Edge;
// Declared up front so kruskal can call it before it is defined further down.
static int find(int* parent, int x);
// kruskal returns the total weight of a minimum spanning tree over n nodes.
int kruskal(int n, Edge* edges, int edgesSize) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
}#include <stdlib.h>
typedef struct {
int u, v, weight;
} Edge;
// qsort takes a comparator function rather than an inline closure.
static int byWeight(const void* a, const void* b) {
const Edge* x = a;
const Edge* y = b;
return (x->weight > y->weight) - (x->weight < y->weight);
}
// Declared up front so kruskal can call it before it is defined further down.
static int find(int* parent, int x);
// kruskal returns the total weight of a minimum spanning tree over n nodes.
int kruskal(int n, Edge* edges, int edgesSize) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
qsort(edges, (size_t)edgesSize, sizeof(Edge), byWeight);
}#include <stdlib.h>
typedef struct {
int u, v, weight;
} Edge;
// qsort takes a comparator function rather than an inline closure.
static int byWeight(const void* a, const void* b) {
const Edge* x = a;
const Edge* y = b;
return (x->weight > y->weight) - (x->weight < y->weight);
}
// Declared up front so kruskal can call it before it is defined further down.
static int find(int* parent, int x);
// kruskal returns the total weight of a minimum spanning tree over n nodes.
int kruskal(int n, Edge* edges, int edgesSize) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
qsort(edges, (size_t)edgesSize, sizeof(Edge), byWeight);
// 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).
}#include <stdlib.h>
typedef struct {
int u, v, weight;
} Edge;
// qsort takes a comparator function rather than an inline closure.
static int byWeight(const void* a, const void* b) {
const Edge* x = a;
const Edge* y = b;
return (x->weight > y->weight) - (x->weight < y->weight);
}
// Declared up front so kruskal can call it before it is defined further down.
static int find(int* parent, int x);
// kruskal returns the total weight of a minimum spanning tree over n nodes.
int kruskal(int n, Edge* edges, int edgesSize) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
qsort(edges, (size_t)edgesSize, sizeof(Edge), byWeight);
// 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).
int* parent = malloc((size_t)n * sizeof(int));
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}#include <stdlib.h>
typedef struct {
int u, v, weight;
} Edge;
// qsort takes a comparator function rather than an inline closure.
static int byWeight(const void* a, const void* b) {
const Edge* x = a;
const Edge* y = b;
return (x->weight > y->weight) - (x->weight < y->weight);
}
// Declared up front so kruskal can call it before it is defined further down.
static int find(int* parent, int x);
// kruskal returns the total weight of a minimum spanning tree over n nodes.
int kruskal(int n, Edge* edges, int edgesSize) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
qsort(edges, (size_t)edgesSize, sizeof(Edge), byWeight);
// 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).
int* parent = malloc((size_t)n * sizeof(int));
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
// find returns the representative of x's set, compressing the path as it goes.
#include <stdlib.h>
typedef struct {
int u, v, weight;
} Edge;
// qsort takes a comparator function rather than an inline closure.
static int byWeight(const void* a, const void* b) {
const Edge* x = a;
const Edge* y = b;
return (x->weight > y->weight) - (x->weight < y->weight);
}
// Declared up front so kruskal can call it before it is defined further down.
static int find(int* parent, int x);
// kruskal returns the total weight of a minimum spanning tree over n nodes.
int kruskal(int n, Edge* edges, int edgesSize) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
qsort(edges, (size_t)edgesSize, sizeof(Edge), byWeight);
// 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).
int* parent = malloc((size_t)n * sizeof(int));
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
// find returns the representative of x's set, compressing the path as it goes.
static int find(int* parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}#include <stdlib.h>
typedef struct {
int u, v, weight;
} Edge;
// qsort takes a comparator function rather than an inline closure.
static int byWeight(const void* a, const void* b) {
const Edge* x = a;
const Edge* y = b;
return (x->weight > y->weight) - (x->weight < y->weight);
}
// Declared up front so kruskal can call it before it is defined further down.
static int find(int* parent, int x);
// kruskal returns the total weight of a minimum spanning tree over n nodes.
int kruskal(int n, Edge* edges, int edgesSize) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
qsort(edges, (size_t)edgesSize, sizeof(Edge), byWeight);
// 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).
int* parent = malloc((size_t)n * sizeof(int));
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// total = summed weight of chosen edges; used = how many we've added so far.
}
// find returns the representative of x's set, compressing the path as it goes.
static int find(int* parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}#include <stdlib.h>
typedef struct {
int u, v, weight;
} Edge;
// qsort takes a comparator function rather than an inline closure.
static int byWeight(const void* a, const void* b) {
const Edge* x = a;
const Edge* y = b;
return (x->weight > y->weight) - (x->weight < y->weight);
}
// Declared up front so kruskal can call it before it is defined further down.
static int find(int* parent, int x);
// kruskal returns the total weight of a minimum spanning tree over n nodes.
int kruskal(int n, Edge* edges, int edgesSize) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
qsort(edges, (size_t)edgesSize, sizeof(Edge), byWeight);
// 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).
int* parent = malloc((size_t)n * sizeof(int));
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// total = summed weight of chosen edges; used = how many we've added so far.
int total = 0, used = 0;
}
// find returns the representative of x's set, compressing the path as it goes.
static int find(int* parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}#include <stdlib.h>
typedef struct {
int u, v, weight;
} Edge;
// qsort takes a comparator function rather than an inline closure.
static int byWeight(const void* a, const void* b) {
const Edge* x = a;
const Edge* y = b;
return (x->weight > y->weight) - (x->weight < y->weight);
}
// Declared up front so kruskal can call it before it is defined further down.
static int find(int* parent, int x);
// kruskal returns the total weight of a minimum spanning tree over n nodes.
int kruskal(int n, Edge* edges, int edgesSize) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
qsort(edges, (size_t)edgesSize, sizeof(Edge), byWeight);
// 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).
int* parent = malloc((size_t)n * sizeof(int));
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// total = summed weight of chosen edges; used = how many we've added so far.
int total = 0, used = 0;
// Which components do this edge's two endpoints currently belong to?
}
// find returns the representative of x's set, compressing the path as it goes.
static int find(int* parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}#include <stdlib.h>
typedef struct {
int u, v, weight;
} Edge;
// qsort takes a comparator function rather than an inline closure.
static int byWeight(const void* a, const void* b) {
const Edge* x = a;
const Edge* y = b;
return (x->weight > y->weight) - (x->weight < y->weight);
}
// Declared up front so kruskal can call it before it is defined further down.
static int find(int* parent, int x);
// kruskal returns the total weight of a minimum spanning tree over n nodes.
int kruskal(int n, Edge* edges, int edgesSize) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
qsort(edges, (size_t)edgesSize, sizeof(Edge), byWeight);
// 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).
int* parent = malloc((size_t)n * sizeof(int));
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// total = summed weight of chosen edges; used = how many we've added so far.
int total = 0, used = 0;
for (int k = 0; k < edgesSize; k++) {
// Which components do this edge's two endpoints currently belong to?
Edge e = edges[k];
int ru = find(parent, e.u), rv = find(parent, e.v);
}
}
// find returns the representative of x's set, compressing the path as it goes.
static int find(int* parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}#include <stdlib.h>
typedef struct {
int u, v, weight;
} Edge;
// qsort takes a comparator function rather than an inline closure.
static int byWeight(const void* a, const void* b) {
const Edge* x = a;
const Edge* y = b;
return (x->weight > y->weight) - (x->weight < y->weight);
}
// Declared up front so kruskal can call it before it is defined further down.
static int find(int* parent, int x);
// kruskal returns the total weight of a minimum spanning tree over n nodes.
int kruskal(int n, Edge* edges, int edgesSize) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
qsort(edges, (size_t)edgesSize, sizeof(Edge), byWeight);
// 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).
int* parent = malloc((size_t)n * sizeof(int));
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// total = summed weight of chosen edges; used = how many we've added so far.
int total = 0, used = 0;
for (int k = 0; k < edgesSize; k++) {
// Which components do this edge's two endpoints currently belong to?
Edge e = edges[k];
int ru = find(parent, e.u), rv = find(parent, e.v);
// Same component already? Adding this edge would close a cycle — skip it.
}
}
// find returns the representative of x's set, compressing the path as it goes.
static int find(int* parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}#include <stdlib.h>
typedef struct {
int u, v, weight;
} Edge;
// qsort takes a comparator function rather than an inline closure.
static int byWeight(const void* a, const void* b) {
const Edge* x = a;
const Edge* y = b;
return (x->weight > y->weight) - (x->weight < y->weight);
}
// Declared up front so kruskal can call it before it is defined further down.
static int find(int* parent, int x);
// kruskal returns the total weight of a minimum spanning tree over n nodes.
int kruskal(int n, Edge* edges, int edgesSize) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
qsort(edges, (size_t)edgesSize, sizeof(Edge), byWeight);
// 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).
int* parent = malloc((size_t)n * sizeof(int));
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// total = summed weight of chosen edges; used = how many we've added so far.
int total = 0, used = 0;
for (int k = 0; k < edgesSize; k++) {
// Which components do this edge's two endpoints currently belong to?
Edge e = edges[k];
int ru = find(parent, e.u), rv = find(parent, e.v);
// Same component already? Adding this edge would close a cycle — skip it.
if (ru == rv) {
continue;
}
}
}
// find returns the representative of x's set, compressing the path as it goes.
static int find(int* parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}#include <stdlib.h>
typedef struct {
int u, v, weight;
} Edge;
// qsort takes a comparator function rather than an inline closure.
static int byWeight(const void* a, const void* b) {
const Edge* x = a;
const Edge* y = b;
return (x->weight > y->weight) - (x->weight < y->weight);
}
// Declared up front so kruskal can call it before it is defined further down.
static int find(int* parent, int x);
// kruskal returns the total weight of a minimum spanning tree over n nodes.
int kruskal(int n, Edge* edges, int edgesSize) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
qsort(edges, (size_t)edgesSize, sizeof(Edge), byWeight);
// 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).
int* parent = malloc((size_t)n * sizeof(int));
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// total = summed weight of chosen edges; used = how many we've added so far.
int total = 0, used = 0;
for (int k = 0; k < edgesSize; k++) {
// Which components do this edge's two endpoints currently belong to?
Edge e = edges[k];
int ru = find(parent, e.u), rv = find(parent, 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.
}
}
// find returns the representative of x's set, compressing the path as it goes.
static int find(int* parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}#include <stdlib.h>
typedef struct {
int u, v, weight;
} Edge;
// qsort takes a comparator function rather than an inline closure.
static int byWeight(const void* a, const void* b) {
const Edge* x = a;
const Edge* y = b;
return (x->weight > y->weight) - (x->weight < y->weight);
}
// Declared up front so kruskal can call it before it is defined further down.
static int find(int* parent, int x);
// kruskal returns the total weight of a minimum spanning tree over n nodes.
int kruskal(int n, Edge* edges, int edgesSize) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
qsort(edges, (size_t)edgesSize, sizeof(Edge), byWeight);
// 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).
int* parent = malloc((size_t)n * sizeof(int));
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// total = summed weight of chosen edges; used = how many we've added so far.
int total = 0, used = 0;
for (int k = 0; k < edgesSize; k++) {
// Which components do this edge's two endpoints currently belong to?
Edge e = edges[k];
int ru = find(parent, e.u), rv = find(parent, 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++;
}
}
// find returns the representative of x's set, compressing the path as it goes.
static int find(int* parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}#include <stdlib.h>
typedef struct {
int u, v, weight;
} Edge;
// qsort takes a comparator function rather than an inline closure.
static int byWeight(const void* a, const void* b) {
const Edge* x = a;
const Edge* y = b;
return (x->weight > y->weight) - (x->weight < y->weight);
}
// Declared up front so kruskal can call it before it is defined further down.
static int find(int* parent, int x);
// kruskal returns the total weight of a minimum spanning tree over n nodes.
int kruskal(int n, Edge* edges, int edgesSize) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
qsort(edges, (size_t)edgesSize, sizeof(Edge), byWeight);
// 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).
int* parent = malloc((size_t)n * sizeof(int));
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// total = summed weight of chosen edges; used = how many we've added so far.
int total = 0, used = 0;
for (int k = 0; k < edgesSize; k++) {
// Which components do this edge's two endpoints currently belong to?
Edge e = edges[k];
int ru = find(parent, e.u), rv = find(parent, 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.
}
}
// find returns the representative of x's set, compressing the path as it goes.
static int find(int* parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}#include <stdlib.h>
typedef struct {
int u, v, weight;
} Edge;
// qsort takes a comparator function rather than an inline closure.
static int byWeight(const void* a, const void* b) {
const Edge* x = a;
const Edge* y = b;
return (x->weight > y->weight) - (x->weight < y->weight);
}
// Declared up front so kruskal can call it before it is defined further down.
static int find(int* parent, int x);
// kruskal returns the total weight of a minimum spanning tree over n nodes.
int kruskal(int n, Edge* edges, int edgesSize) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
qsort(edges, (size_t)edgesSize, sizeof(Edge), byWeight);
// 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).
int* parent = malloc((size_t)n * sizeof(int));
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// total = summed weight of chosen edges; used = how many we've added so far.
int total = 0, used = 0;
for (int k = 0; k < edgesSize; k++) {
// Which components do this edge's two endpoints currently belong to?
Edge e = edges[k];
int ru = find(parent, e.u), rv = find(parent, 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;
}
}
free(parent);
return total; // O(E log E), dominated by the sort
}
// find returns the representative of x's set, compressing the path as it goes.
static int find(int* parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}#include <algorithm>
#include <vector>
using namespace std;
struct Edge {
int u, v, weight;
};
class Solution {
public:
// kruskal returns the total weight of a minimum spanning tree over n nodes.
int kruskal(int n, vector<Edge>& edges) {
}
};#include <algorithm>
#include <vector>
using namespace std;
struct Edge {
int u, v, weight;
};
class Solution {
public:
// kruskal returns the total weight of a minimum spanning tree over n nodes.
int kruskal(int n, vector<Edge>& edges) {
// Greedy idea: an MST never needs a heavier edge when a lighter one keeps the
// graph acyclic. So examine edges from lightest to heaviest.
}
};#include <algorithm>
#include <vector>
using namespace std;
struct Edge {
int u, v, weight;
};
class Solution {
public:
// kruskal returns the total weight of a minimum spanning tree over n nodes.
int kruskal(int n, vector<Edge>& edges) {
// 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(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
return a.weight < b.weight;
});
}
};#include <algorithm>
#include <vector>
using namespace std;
struct Edge {
int u, v, weight;
};
class Solution {
public:
// kruskal returns the total weight of a minimum spanning tree over n nodes.
int kruskal(int n, vector<Edge>& edges) {
// 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(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
return a.weight < b.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).
}
};#include <algorithm>
#include <vector>
using namespace std;
struct Edge {
int u, v, weight;
};
class Solution {
public:
// kruskal returns the total weight of a minimum spanning tree over n nodes.
int kruskal(int n, vector<Edge>& edges) {
// 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(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
return a.weight < b.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).
vector<int> parent(n);
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
};#include <algorithm>
#include <vector>
using namespace std;
struct Edge {
int u, v, weight;
};
class Solution {
public:
// kruskal returns the total weight of a minimum spanning tree over n nodes.
int kruskal(int n, vector<Edge>& edges) {
// 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(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
return a.weight < b.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).
vector<int> parent(n);
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
private:
// find returns the representative of x's set, compressing the path as it goes.
};#include <algorithm>
#include <vector>
using namespace std;
struct Edge {
int u, v, weight;
};
class Solution {
public:
// kruskal returns the total weight of a minimum spanning tree over n nodes.
int kruskal(int n, vector<Edge>& edges) {
// 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(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
return a.weight < b.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).
vector<int> parent(n);
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
private:
// find returns the representative of x's set, compressing the path as it goes.
int find(vector<int>& parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}
};#include <algorithm>
#include <vector>
using namespace std;
struct Edge {
int u, v, weight;
};
class Solution {
public:
// kruskal returns the total weight of a minimum spanning tree over n nodes.
int kruskal(int n, vector<Edge>& edges) {
// 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(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
return a.weight < b.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).
vector<int> parent(n);
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// total = summed weight of chosen edges; used = how many we've added so far.
}
private:
// find returns the representative of x's set, compressing the path as it goes.
int find(vector<int>& parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}
};#include <algorithm>
#include <vector>
using namespace std;
struct Edge {
int u, v, weight;
};
class Solution {
public:
// kruskal returns the total weight of a minimum spanning tree over n nodes.
int kruskal(int n, vector<Edge>& edges) {
// 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(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
return a.weight < b.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).
vector<int> parent(n);
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// total = summed weight of chosen edges; used = how many we've added so far.
int total = 0, used = 0;
}
private:
// find returns the representative of x's set, compressing the path as it goes.
int find(vector<int>& parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}
};#include <algorithm>
#include <vector>
using namespace std;
struct Edge {
int u, v, weight;
};
class Solution {
public:
// kruskal returns the total weight of a minimum spanning tree over n nodes.
int kruskal(int n, vector<Edge>& edges) {
// 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(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
return a.weight < b.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).
vector<int> parent(n);
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// total = summed weight of chosen edges; used = how many we've added so far.
int total = 0, used = 0;
// Which components do this edge's two endpoints currently belong to?
}
private:
// find returns the representative of x's set, compressing the path as it goes.
int find(vector<int>& parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}
};#include <algorithm>
#include <vector>
using namespace std;
struct Edge {
int u, v, weight;
};
class Solution {
public:
// kruskal returns the total weight of a minimum spanning tree over n nodes.
int kruskal(int n, vector<Edge>& edges) {
// 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(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
return a.weight < b.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).
vector<int> parent(n);
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// total = summed weight of chosen edges; used = how many we've added so far.
int total = 0, used = 0;
for (const Edge& e : edges) {
// Which components do this edge's two endpoints currently belong to?
int ru = find(parent, e.u), rv = find(parent, e.v);
}
}
private:
// find returns the representative of x's set, compressing the path as it goes.
int find(vector<int>& parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}
};#include <algorithm>
#include <vector>
using namespace std;
struct Edge {
int u, v, weight;
};
class Solution {
public:
// kruskal returns the total weight of a minimum spanning tree over n nodes.
int kruskal(int n, vector<Edge>& edges) {
// 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(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
return a.weight < b.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).
vector<int> parent(n);
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// total = summed weight of chosen edges; used = how many we've added so far.
int total = 0, used = 0;
for (const Edge& e : edges) {
// Which components do this edge's two endpoints currently belong to?
int ru = find(parent, e.u), rv = find(parent, e.v);
// Same component already? Adding this edge would close a cycle — skip it.
}
}
private:
// find returns the representative of x's set, compressing the path as it goes.
int find(vector<int>& parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}
};#include <algorithm>
#include <vector>
using namespace std;
struct Edge {
int u, v, weight;
};
class Solution {
public:
// kruskal returns the total weight of a minimum spanning tree over n nodes.
int kruskal(int n, vector<Edge>& edges) {
// 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(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
return a.weight < b.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).
vector<int> parent(n);
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// total = summed weight of chosen edges; used = how many we've added so far.
int total = 0, used = 0;
for (const Edge& e : edges) {
// Which components do this edge's two endpoints currently belong to?
int ru = find(parent, e.u), rv = find(parent, e.v);
// Same component already? Adding this edge would close a cycle — skip it.
if (ru == rv) {
continue;
}
}
}
private:
// find returns the representative of x's set, compressing the path as it goes.
int find(vector<int>& parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}
};#include <algorithm>
#include <vector>
using namespace std;
struct Edge {
int u, v, weight;
};
class Solution {
public:
// kruskal returns the total weight of a minimum spanning tree over n nodes.
int kruskal(int n, vector<Edge>& edges) {
// 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(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
return a.weight < b.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).
vector<int> parent(n);
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// total = summed weight of chosen edges; used = how many we've added so far.
int total = 0, used = 0;
for (const Edge& e : edges) {
// Which components do this edge's two endpoints currently belong to?
int ru = find(parent, e.u), rv = find(parent, 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.
}
}
private:
// find returns the representative of x's set, compressing the path as it goes.
int find(vector<int>& parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}
};#include <algorithm>
#include <vector>
using namespace std;
struct Edge {
int u, v, weight;
};
class Solution {
public:
// kruskal returns the total weight of a minimum spanning tree over n nodes.
int kruskal(int n, vector<Edge>& edges) {
// 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(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
return a.weight < b.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).
vector<int> parent(n);
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// total = summed weight of chosen edges; used = how many we've added so far.
int total = 0, used = 0;
for (const Edge& e : edges) {
// Which components do this edge's two endpoints currently belong to?
int ru = find(parent, e.u), rv = find(parent, 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++;
}
}
private:
// find returns the representative of x's set, compressing the path as it goes.
int find(vector<int>& parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}
};#include <algorithm>
#include <vector>
using namespace std;
struct Edge {
int u, v, weight;
};
class Solution {
public:
// kruskal returns the total weight of a minimum spanning tree over n nodes.
int kruskal(int n, vector<Edge>& edges) {
// 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(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
return a.weight < b.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).
vector<int> parent(n);
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// total = summed weight of chosen edges; used = how many we've added so far.
int total = 0, used = 0;
for (const Edge& e : edges) {
// Which components do this edge's two endpoints currently belong to?
int ru = find(parent, e.u), rv = find(parent, 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.
}
}
private:
// find returns the representative of x's set, compressing the path as it goes.
int find(vector<int>& parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}
};#include <algorithm>
#include <vector>
using namespace std;
struct Edge {
int u, v, weight;
};
class Solution {
public:
// kruskal returns the total weight of a minimum spanning tree over n nodes.
int kruskal(int n, vector<Edge>& edges) {
// 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(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
return a.weight < b.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).
vector<int> parent(n);
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// total = summed weight of chosen edges; used = how many we've added so far.
int total = 0, used = 0;
for (const Edge& e : edges) {
// Which components do this edge's two endpoints currently belong to?
int ru = find(parent, e.u), rv = find(parent, 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
}
private:
// find returns the representative of x's set, compressing the path as it goes.
int find(vector<int>& parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}
};Tap the left half to go back, the right half to go forward.
Arrow keys or space to navigate · Esc to exit.