1754. The Costs Every Cheapest Plan Pays

An UNDIRECTED graph has n vertices and m edges, edge i joining u and v at cost w. Problem 1745 shows that there may be many cheapest plans. Print the COSTS one of them uses, in non-decreasing order, or None when a plan needs no edges.

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

## Why this has one answer even though the plan does not

The second example has three different cheapest plans. They use different EDGES and the same COSTS: every one of them uses 5 twice. That is not a coincidence, it is a theorem:

every cheapest spanning forest of a graph uses the same multiset of costs

So the question is well posed without any tie-break rule, unlike problem 1742 which has to pin one. That is the whole content of this problem, and it is the fact that makes "the cheapest total" and "the smallest possible worst edge" from problem 1747 both well defined at once.

## Why the theorem is true

Let T and T' be two cheapest plans and suppose their cost multisets differ. Take the smallest cost w where they differ, and say T uses w more often. Let T_w be the edges of T of cost at most w, and likewise T'_w.

Both induce the same partition of the vertices, because that partition is determined by the graph alone: two vertices are in one group exactly when the full graph joins them using edges of cost at most w. The forward direction is clear; the other direction is the exchange argument, since a plan joining two such vertices only through a dearer edge could swap that edge for a cheaper one across the same cut and lower its total.

A forest inducing a given partition on n vertices has exactly n minus the number of groups edges. So T_w and T'_w have the same SIZE. They also agree on every cost strictly below w, by the choice of w. So they contain the same number of edges of cost exactly w, which contradicts T using w more often.

## The method

run Kruskal collect the costs of the edges it takes sort them and print them

No tie-break is needed anywhere, and running Kruskal with a different tie-break gives a different edge list and the identical output.

## The three things that have to be said

directed? no. self-loops? allowed, and in no plan, so their costs never appear. parallel edges? allowed, and only the cheaper is used, unless the two are equal in which case one copy appears once. disconnected? allowed, and the list has n - c entries, one per edge of the spanning forest.

## What most people try first

Printing the costs in the order Kruskal took them, which is already non-decreasing and therefore correct by accident. It stops being correct the moment the implementation collects the costs during a Prim-style growth instead, where they come out in no particular order. Sorting explicitly costs O(n log n) and removes the dependence.

The other mistake is to print the DISTINCT costs. The second example then prints 5 rather than 5 5, and the sum of the printed values stops equalling the cheapest total, which is the quickest self-check available here.

## Cost

Time O(m log m), space O(n + m), no recursion. Each printed cost is at most 10^9 and fits in a 32-bit integer; their sum reaches about 2 * 10^14, which is why problem 1741 needs 64 bits and this does not.

## Related

Problem 1741 prints the sum of exactly these numbers. Problem 1747 prints the largest of them. Problem 1745 asks whether the plan achieving them is unique, and problem 1742 has to pin a tie-break because it prints edges rather than costs.

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