1747. The Smallest Possible Worst Link

An UNDIRECTED graph has n vertices and m edges, edge i joining u and v at cost w. A PLAN is a set of edges keeping every pair of vertices joined that was joined before, using no more edges than necessary.

A plan is judged here not by its TOTAL but by its WORST single edge. Print the smallest possible worst edge over all plans, and 0 when a plan needs no edges at all.

4 vertices, 1-2 (1), 2-3 (2), 3-4 (3), 1-4 (9) -> 3 4 vertices, 1-2 (1), 2-3 (9), 3-4 (2), 1-4 (3) -> 3 1 vertex, no edges -> 0 4 vertices, 1-2 (5), 3-4 (7) -> 7 3 vertices, 1-2 (4), 2-3 (4), 1-3 (4) -> 4

The second example is the one to study. The cheapest plan by TOTAL is 1-2 (1), 3-4 (2), 1-4 (3), totalling 6, and its worst edge is 3. No plan has a worst edge below 3, because the edges of cost 1 and 2 alone leave vertex 1 and vertex 4 in different pieces from each other.

## The surprise: the cheapest plan is already the best possible

Any plan that minimises the TOTAL also minimises the WORST EDGE. So the answer is simply the dearest edge the cheapest plan uses, and no separate search is needed.

That is not obvious, and it is worth proving, because the two objectives are different in general. Minimising a total and minimising a maximum usually give different answers; on spanning plans they do not.

## Why it holds

Let T be a cheapest plan by total, with worst edge e of cost W. Suppose some plan S had every edge strictly cheaper than W.

Remove e from T. That splits one piece of T into two parts, A and B, with no edge of T - e crossing between them. Now S joins every pair that was joined, so S has a path from a vertex of A to a vertex of B, and that path crosses from A to B on some edge f, whose cost is strictly below W by assumption.

Then T - e + f is a plan, since f reconnects exactly what e was holding together, and it costs strictly less than T. That contradicts T being cheapest. So no plan has every edge below W, and W is the smallest possible worst edge.

## The three things that have to be said

directed? no. self-loops? allowed, and in no plan, so never the worst edge. parallel edges? allowed, and only the cheaper copy is ever used. disconnected? allowed. The worst edge is taken across the WHOLE forest, so the fourth example answers 7 and not 5.

## What most people try first

A binary search on the answer: guess a limit t, keep only the edges of cost at most t, and check whether that joins everything the full graph joins. That is correct, it is what this problem's oracle does, and it costs O(m log m) with a connectivity pass per guess, so O((n + m) log m) overall. It is a perfectly good solution and strictly more work than reading the answer off Kruskal.

The wrong first attempt is to take the dearest edge of the graph, or the dearest edge that is a bridge. On the second example the dearest edge is 9 and the answer is 3.

## The method

run Kruskal the answer is the largest cost among the edges it takes, or 0 if it takes none

One pass, no extra structure beyond the disjoint set, and the proof above is what licenses it.

## Cost

Time O(m log m) for the sort plus near-constant time per disjoint-set operation. Space O(n + m). No recursion. The answer is a single cost, at most 10^9, so a 32-bit integer holds it; no total is ever formed here.

## Related

Problem 1645 asks for the smallest possible worst edge on a ROUTE between two given vertices, and problem 1015 answers that for many pairs at once. Both are about one pair; this is about the whole network, and the answer here is the largest of all those per-pair answers. Problem 1741 prints the total of the same plan.

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ m ≤ 200000` - `1 ≤ u, v ≤ n` - `1 ≤ w ≤ 1000000000` - `u` may equal `v`, so self-loops can occur, and costs may repeat - the same pair may be listed more than once, so parallel edges can occur - the graph may be disconnected