1748. How Many Links Could Be Used

An UNDIRECTED graph has n vertices and m edges, edge i joining u and v at cost w. There may be several cheapest plans, as problem 1745 decides.

Print how many edges appear in AT LEAST ONE cheapest plan.

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

The second example has three cheapest plans, each using two of the three edges, so all three edges are usable even though no plan holds more than two. That is the whole shape of the question: the answer counts edges, not plans, and it can exceed the size of a single plan.

## The number this is NOT

Problem 1011 counts the edges that appear in EVERY cheapest plan. On the second example above that number is 0 and this one is 3. On the fourth example both are 1. The two questions share an algorithm and give different answers, and reading the wrong one off is the likeliest way to be wrong here.

Problem 1745 compares this count against n - c, the size of one plan, to decide whether the plan is forced at all.

## The three things that have to be said

directed? no. self-loops? allowed, and in no plan, so never counted. parallel edges? allowed, and two copies of the SAME cost are both counted, while two copies of different costs count only the cheaper. disconnected? allowed, and plans are spanning forests.

## What most people try first

Running Kruskal with every possible tie-break and taking the union of the results. The number of tie-breaks is factorial in the size of a cost class, so this is hopeless; and skipping it by running a handful of random tie-breaks undercounts silently.

The second attempt is to say an edge is usable when it is not the dearest edge of any cycle. That is right in spirit and hard to turn into an algorithm, because there are exponentially many cycles.

## One cost class at a time

Process the edges in increasing cost, and handle all edges of ONE cost together:

for each maximal run of edges sharing a cost, in increasing cost order: an edge of the run is usable <=> its two ends lie in different groups BEFORE anything in this run is merged then merge every edge of the run count the usable ones

Testing the whole class before merging any of it is the entire algorithm. If the merging is interleaved, as plain Kruskal does, then on the triangle of equal costs the first two edges merge everything and the third is reported unusable, giving 2 instead of 3.

## Why that test is exactly right

Fix a cost w. Whatever choices a cheapest plan makes among the cheaper edges, the PARTITION of the vertices it produces after all costs below w are processed is the same. That is the standard Kruskal invariant: all cheapest plans agree on the groups formed by each cost threshold, even when they disagree about which edges formed them.

Given that fixed partition:

If an edge of cost w has its ends in different groups, then by the cut property some cheapest plan uses a cheapest edge crossing the cut separating one of those groups from the rest, and this edge is one such cheapest crossing edge, so some cheapest plan uses it.

If its ends are in the same group, then they are already joined using edges of cost at most w, so adding this edge to any plan creates a cycle whose other edges all cost at most w. Removing this edge from that cycle keeps the plan spanning and costs no more, so no cheapest plan needs it. More carefully: if some plan did use it, the cycle it closes with the cheaper-or-equal edges contains an edge of cost at most w outside the plan, and swapping gives a plan no dearer without it, so its total is not reduced by keeping it. Hence it lies in no cheapest plan when its ends were already joined strictly below w, and when they were joined by other edges of exactly w it is itself in that class and tested before any of them merged, so the test still sees different groups.

## 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. The answer is at most m, so a 32-bit integer holds it.

## Related

Problem 1011 counts the edges in EVERY cheapest plan. Problem 1745 uses this count to decide uniqueness. Problem 1751 answers this question per edge rather than as a total, and problem 1752 does the same for the "every plan" version.

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