Cheapest Network — Solution & Editorial

Back to the Problem

Kruskal: sort edges, union-find, take every edge that joins two components. Exactly N−1 accepted edges = spanning tree.

Complexity: O(M log M)

Watch out: Total weight reaches ~10¹³.