1742. Which Links the Cheapest Plan Uses

An UNDIRECTED graph has n vertices and m edges, numbered 1 to m in the order they are listed, edge i joining u and v at cost w. Problem 1741 prints the cheapest total; this prints WHICH edges to use.

Print the numbers of the chosen edges in increasing order, or None if no edge is chosen at all.

Costs may repeat, so there can be several cheapest sets, and the answer is pinned by the rule Kruskal's algorithm follows:

consider the edges in order of increasing cost among edges of equal cost, consider the one listed EARLIER in the input first take an edge exactly when its two ends are not already joined

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) -> 1 2 1 vertex, no edges -> None 2 vertices, 1-2 (4), 1-2 (4) -> 1

The second example is the one to look at. All three costs are 5, so all three pairs of edges are equally cheap; the rule takes the two listed first.

## The three things that have to be said

directed? no. self-loops? allowed, and never chosen. parallel edges? allowed, and only the first of two equally cheap copies is chosen, which is exactly what the tie-break decides. disconnected? allowed, and the answer is a forest of n - c edges.

## Why the answer has to be pinned at all

With repeated costs the cheapest set is genuinely not unique. On the second example above, {1,2}, {1,3} and {2,3} all cost 10, and no property of the graph prefers one. Problem 1745 asks whether that ambiguity exists at all, and problem 1748 asks which edges could appear in SOME cheapest set. Here the input order settles it, which also makes the output reproducible between two correct implementations.

The practical consequence is that the sort must be STABLE on cost, or equivalent to sorting by the pair (cost, index). A sort that reorders equal costs arbitrarily gives a cheapest set with the right TOTAL and the wrong list, which is the single most likely way to fail this problem while passing problem 1741.

## The method

sort the edge indices by (cost, index) every vertex starts in its own group for each index in that order: if the two ends are in different groups: record the index, merge the groups print the recorded indices sorted increasingly

Recording then sorting matters: the indices are recorded in cost order, not in numeric order, and the output asks for numeric order. On the first example they happen to coincide; on a graph whose cheapest edge is listed last they do not.

## Why the result really is cheapest

The cut property. For any way of splitting the vertices into two sides, some cheapest forest uses a cheapest edge crossing the split. When Kruskal takes an edge, every cheaper edge has already been examined, so no cheaper edge crosses between the group of one endpoint and the rest; the edge taken is therefore a cheapest crossing edge for that split and is safe. Taking only safe edges, and exactly n - c of them, gives a cheapest forest.

## Cost

Time O(m log m) for the sort plus near-constant time per group operation, and O(m log m) again to sort the output. Space O(n + m). No recursion, which matters because a path of 200000 vertices is permitted. The costs are at most 10^9 each and are never added up here, so nothing can overflow a 32-bit integer; problem 1741, which does add them, needs 64 bits.

## Related

Problem 1741 prints the total. Problem 1745 asks whether the choice was forced, problem 1748 counts the edges that appear in at least one cheapest set, and problem 1751 answers that per edge.

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