Build MST using Kruskal or Prim algorithms
Pick edges that connect new components with minimum weight without forming cycles.
Use on connected weighted undirected graphs to minimize total edge cost.
Kruskal with DSU over sorted edges, or Prim growing a frontier with a min-heap to connect all vertices at minimal total cost.
# 1D DP Templates
def kadane(nums):
best = cur = nums[0]
for x in nums[1:]:
cur = max(x, cur+x)
best = max(best, cur)
return best
def house_robber(nums):
prev2 = 0; prev1 = 0
for v in nums:
prev2, prev1 = prev1, max(prev1, prev2+v)
return prev1Sort edges and union if components differ
def kruskal(n, edges):
# edges: (w,u,v)
dsu=DSU(n); edges.sort()
cost=0; mst=[]
for w,u,v in edges:
if dsu.union(u,v): cost+=w; mst.append((u,v,w))
return cost, mstGrow from a node using a min-heap
import heapq
def prim(n, adj):
# adj[u] = [(v,w), ...]; assumes connected
vis=[False]*n; vis[0]=True; h=[]
for v,w in adj[0]: heapq.heappush(h, (w, 0, v))
cost=0; cnt=1
while h and cnt<n:
w,u,v = heapq.heappop(h)
if vis[v]: continue
vis[v]=True; cost+=w; cnt+=1
for nv,nw in adj[v]:
if not vis[nv]: heapq.heappush(h, (nw, v, nv))
return cost