1011. The Cables No Cheapest Plan Can Skip

A network has n stations and m two-way cables, cable i joining u and v at price w. A PLAN is a set of cables leaving every station reachable from every other, and a CHEAPEST plan is one whose total price is as small as possible. There may be many cheapest plans.

A cable is CRITICAL when EVERY cheapest plan uses it. Print how many cables are critical, or -1 if the network cannot be connected at all.

4 stations, cables 1-2 (1), 2-3 (2), 3-4 (3), 4-1 (4), 1-3 (5) -> 3 3 stations, cables 1-2 (1), 2-3 (1), 1-3 (1) -> 0 4 stations, cables 1-2 (1), 3-4 (1) -> -1 2 stations, cables 1-2 (5), 1-2 (5) -> 0

The second example is a triangle of equal prices. Any two of the three cables form a cheapest plan, so no single cable is in all of them and the answer is 0. The fourth is the same idea with only two cables: the pair must be connected, but either copy will do.

## What most people try first

Take one cheapest plan and count its cables. That answers n - 1 every time and is wrong whenever there is a tie, which is exactly when the question is interesting. It gives 2 on the triangle instead of 0.

The second attempt is to call a cable critical when it is the unique cheapest cable across some cut. That is the right idea and it is awkward to turn into code, because the cuts are not given.

## Remove it and see whether the price goes up

W = cheapest plan price over all the cables if the network cannot be connected: print -1 count = 0 for each cable i: W2 = cheapest plan price with cable i deleted if W2 does not exist, or W2 > W: count = count + 1 print count

Each inner computation is one Kruskal sweep over the sorted cables with one index skipped, so sorting is done ONCE outside the loop and only the disjoint set is rebuilt.

## Why removing and comparing is exactly the definition

If deleting cable i raises the cheapest price or breaks the network, then no plan avoiding i reaches W, so every cheapest plan contains i and it is critical.

If deleting i leaves the price at W, then the plan found without i is a cheapest plan that does not use i, so i is not in every cheapest plan and it is not critical.

The two directions cover every cable, which is why nothing subtler is needed.

## Why the duplicates take care of themselves

Two cables between the same pair at the same price are separate entries, and removing one leaves the other, so the price does not move and neither is critical. There is no rule about duplicates anywhere in the method; it is a consequence.

## The one that is easy to get wrong

A cable so expensive that no plan would ever use it is NOT critical, and the test says so: removing it does not change the cheapest price. A check phrased as "is this cable in the plan I computed" gets that right by luck and gets the triangle wrong.

## Overflow

n - 1 cables at 10^9 total 2 * 10^11 at these limits, past the 2147483647 a signed 32 bit integer holds. Both W and every W2 must be 64 bit, and comparing two wrapped values can easily report a smaller price as larger.

## Cross-reference

Problem 389 computes the cheapest total itself, which is the W this problem starts from. Problem 1010 maximises rather than minimises. This one asks about the STRUCTURE of the set of optimal answers rather than about one of them, which is a different kind of question and is why the limits here are much smaller.

## Cost

Time O(m log m + m * (m + n) alpha(n)), which is about 10^5 operations at m = 300. Space O(n + m).

Constraints - `1 ≤ n ≤ 200` - `0 ≤ m ≤ 300` - `1 ≤ u, v ≤ n` and `u` is never equal to `v`. - `1 ≤ w ≤ 1000000000` - The same pair may be cabled more than once.