1751. Could This Link Be Used

An UNDIRECTED graph has n vertices and m edges, edge i joining u and v at cost w. Problem 1748 counts the edges that appear in at least one cheapest plan. This asks about each edge in turn.

For EACH edge, in the order it was listed, print Yes if some cheapest plan uses it and No if none does. Print None when m is 0.

1-2 (5), 2-3 (5), 1-3 (5) -> Yes Yes Yes 1-2 (4), 1-2 (7) -> Yes No 1-1 (3) -> No 1-2 (1), 2-3 (2), 1-3 (2) -> Yes Yes Yes

The last example is worth checking. The cheapest plan costs 3 and uses 1-2 plus either edge of cost 2, so all three edges are usable even though a plan holds two.

## Why the per-edge answer and not a count

Two reasons. A count hides WHICH edges are flexible, which is the information a network planner actually wants: it says exactly which cables could be swapped for another at no extra cost.

And it forces an answer for every edge, including the ones the algorithm never looks at. A self-loop is answered No, and so is the dearer of two parallel edges. A solution that collects usable edges into a set and prints the set never has to decide what those cases do.

## The three things that have to be said

directed? no. self-loops? allowed, and always No. parallel edges? allowed, and two copies of the SAME cost are both Yes, while two copies of different costs give Yes then No. disconnected? allowed, and plans are spanning forests.

## What most people try first

Running Kruskal once and answering Yes for the edges it takes. That gives exactly n - c yes answers and the right answer can have more, which is precisely problem 1745's question. On the triangle of equal costs it answers Yes Yes No and all three edges are usable.

The second attempt is to re-run Kruskal m times, once per edge, each time forcing that edge in first and comparing the total against the cheapest. That is correct and costs O(m^2 log m), which at m = 200000 is 4 * 10^10 sorted passes.

## One pass, a whole cost class at a time

sort the edges by cost for each maximal run of edges sharing a cost: pass 1: mark edge i as Yes when its two ends are in different groups pass 2: merge every edge of the run then print the marks in INPUT order

Two things make this work. Testing the whole class before merging any of it, because two edges of one cost may be alternatives for each other; and marking an ARRAY indexed by the edge's input position, so the output comes out in the right order even though the work happens in cost order.

## Why the test is exactly right

Fix a cost w and let P be the partition of the vertices into groups joined by edges strictly cheaper than w. Every cheapest plan induces the same P, which is the standard Kruskal invariant.

If an edge of cost w has its ends in different groups of P, it is a cheapest edge crossing the cut that separates one of those groups from the rest, because everything cheaper is internal. The cut property then gives a cheapest plan using it: take any cheapest plan, add the edge, and drop the dearest edge of the cycle that crosses that cut, which costs at least w.

If both ends are in the same group of P, they are already joined by cheaper edges, so adding this edge to any plan makes a cycle all of whose other edges are cheaper. Dropping this edge instead keeps the plan spanning and strictly cheaper, so no cheapest plan contains it.

## Cost

Time O(m log m), space O(n + m), no recursion. Nothing is summed, so a 32-bit integer suffices throughout.

## Related

Problem 1748 is the count. Problem 1752 asks the opposite question per edge, whether EVERY cheapest plan uses it, and the two answers together classify each edge as forced, optional or useless. Problem 1745 asks whether any edge is optional at all.

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