Graph Exploration Target: 15s
Sort edges by weight. Greedily add edge if it connects two components (Union-Find). Stop at n-1 edges.
def kruskal(n, edges):
# edges = [(weight, u, v), ...]
edges.sort()
uf = UnionFind(n)
mst_weight = 0
mst_edges = 0
for w, u, v in edges:
if uf.union(u, v):
mst_weight += w
mst_edges += 1
if mst_edges == n - 1:
break
return mst_weight if mst_edges == n - 1 else -1Type it from memory. Go.