Minimize Maximum Component Cost

Establish the objective before coding

This title is not enough to determine a unique algorithm. Ask whether a component cost is its size, sum of node weights, maximum edge weight, or something else; ask which edges may be removed or added and whether there is an operation budget. Many versions become a minimax problem: for a proposed threshold T, test whether the allowed operations can ensure every resulting component costs at most T. Only after that feasibility predicate is precisely defined should you binary-search the answer.

Build the right predicate

For a tree, feasibility may be a postorder traversal that cuts an edge whenever a subtree would exceed T. For an arbitrary graph, it may require DSU, minimum spanning structure, or be computationally different altogether. State the invariant: the predicate must return true exactly when threshold T is achievable, and it must be monotone so that a larger threshold never becomes infeasible. Complexity is commonly O((n+m) log R) when each feasibility pass is O(n+m) over answer range R, but give that bound only after the actual operations are known. Test disconnected graphs, one component, and weights exceeding 32-bit totals.