The problem
When several lines cost the same, there can be many cheapest spanning trees. For each line in edges, answer True if at least one cheapest spanning tree uses it, and False if none does. If the network is not connected, the question is about cheapest spanning forests: a cheapest tree for each connected part.
edges = [(0, 1, 1), (1, 2, 2), (0, 2, 2),
(2, 3, 3), (1, 3, 5)]
in_some_mst(4, edges)
# [True, True, True, True, False]
1–2 and 0–2 cost the same and close a loop with 0–1, so each of them is in some cheapest tree. 1–3 is the most expensive line on the loop 1 → 2 → 3 → 1, so it is in none.
Limits
- Up to 100,000 stations and about 200,000 lines.
- Many lines may share a cost. A fresh search for every line is far too slow. The big tests have 4 seconds each.
Builds on SPAN-4 The cut property.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | The example | Not run | |
| 2 | A triangle of equal lines | Not run | |
| 3 | A triangle of different lines | Not run | |
| 4 | A loop and repeated lines | Not run | |
| 5 | Two separate parts | Not run | |
| 6 | Equal, but joined by cheaper lines | Not run | |
| 7 | Order of the list does not matter | Not run | |
| 8 | 100,000 stations, few different costs | Not run | |
| 9 | 100,000 stations, all costs different | Not run |