Minimize Maximum Component Cost

Partition a connected weighted graph by removing edges so you have at most k components and the cost (max edge weight) of each component is minimized. This reduces to finding the smallest threshold T such that keeping only edges with weight ≤ T yields ≤ k connected components — a monotonic predicate you can check with union-find and binary search over edge weights.