1745. Is the Cheapest Plan Forced

An UNDIRECTED graph has n vertices and m edges, edge i joining u and v at cost w. Problem 1741 finds the cheapest total. Print Yes if there is only ONE set of edges achieving it, and No if two or more different sets do.

4 vertices, 1-2 (1), 2-3 (2), 3-4 (3), 1-4 (9) -> Yes 3 vertices, 1-2 (5), 2-3 (5), 1-3 (5) -> No any two of the three 2 vertices, 1-2 (4), 1-2 (4) -> No either copy will do 1 vertex, no edges -> Yes only the empty set 4 vertices, 1-2 (5), 3-4 (7) -> Yes

The question is about the SET OF EDGES, not the total. Two different sets with the same total count as two, which is exactly what makes the answer No in the second and third examples.

## The three things that have to be said

directed? no. self-loops? allowed, and never in any cheapest set, so they never make the answer No. parallel edges? allowed, and two copies of equal cost always make it No. disconnected? allowed, and the question is about the cheapest spanning FOREST, so each piece contributes.

## What most people try first

Running Kruskal twice with different tie-breaks and comparing the results. That can prove No and it can never prove Yes, because two particular tie-breaks agreeing says nothing about a third.

The second attempt is to look for repeated costs and answer No whenever any two edges share a cost. Repeated costs are NECESSARY for ambiguity and not sufficient. On 1-2 (1), 2-3 (1), 3-1 (5) the cost 1 appears twice and the cheapest set is still forced: both cheap edges have to be used, because dropping either one forces the edge of cost 5 in and raises the total. There is a test below for exactly that graph, and it answers Yes.

## The clean criterion

Count the edges that lie in AT LEAST ONE cheapest forest, which problem 1748 asks for directly, and compare with the forest's size:

answer Yes <=> (number of edges that lie in some cheapest forest) == n - c

where c is the number of connected pieces, so n - c is how many edges a spanning forest holds.

Why: every cheapest forest has exactly n - c edges, and every one of them lies in some cheapest forest, so the count is at least n - c. If it is exactly n - c, then there is only one candidate set and it must be the unique answer. If it is more, some edge e lies in a cheapest forest F and some other edge f lies in a cheapest forest F' with f not in F, so F and F' differ.

## Counting the usable edges, one cost at a time

Walk the edges in order of increasing cost and handle all edges of one cost TOGETHER:

for each group of edges sharing a cost, in increasing cost order: an edge of the group is usable <=> its two ends are in different groups BEFORE any edge of this cost is merged then merge every edge of the group

The reason the whole cost class has to be examined before any of it is merged: two edges of the same cost may be alternatives for each other, and merging the first would make the second look useless when in fact either could be chosen. That single detail is the difference between this and problem 1742's loop, and getting it wrong reports Yes on the three-equal-costs example.

## Cost

Time O(m log m) for the sort plus near-constant time per disjoint-set operation. Space O(n + m). No recursion, which matters at n = 200000. No sums are formed, so nothing overflows a 32-bit integer.

## Related

Problem 1748 counts the usable edges, which this compares against a size. Problem 1746 asks what the next cheapest total is, and problem 1751 answers the usable question per edge. Problem 1011 counts the edges that are in EVERY cheapest plan, which is a different number.

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