Connect everything for the least money
Join all the places with the cheapest set of roads, by taking roads from cheapest to dearest and skipping any that would make a loop. About 16 minutes.
Cheapest first, skip loops
Here's a simple idea. Line up all the roads from cheapest to most expensive. Go through them one at a time. For each road, ask: are its two ends already connected through roads we have chosen? If not, take the road. If yes, skip it, because it would only make a loop.
To answer that question quickly, use union-find, which tracks groups of connected places. Each time you take a road, merge the two groups.
parent = list(range(n)) ra, rb = find(a), find(b)
- roads
- 1
- total
- 1
Sorted: 1, 2, 3, 4, 5, 8. The cheapest road, 0 to 2 for 1, joins two separate places. Take it.
Done when n minus one roads are taken
A tree that joins n places has exactly n - 1 roads. So count the roads you take. If you reach n - 1, everything is connected and the total is your answer.
If you run out of roads with fewer than n - 1 taken, some places can't be reached at all, so the answer is -1. A single place needs no roads, so its cost is 0.
used += 1
if used == n - 1:
break # a tree has n - 1 edgesThe next cheapest road joins two places that are already connected through roads you've chosen. What do you do?
- ASkip it, because it would form a loop and waste money
- BTake it, because it is cheap
- CTake it and drop a more expensive road
Show the answer
Skip it, because it would form a loop and waste money. The two ends are already connected, so the road adds cost but no new connection.
Cheapest way to connect everything
There are n villages, numbered 0 to n − 1. roads[i] = [a, b, cost] is a possible two-way road between village a and village b with the given cost. Choose some of the roads so that every village can reach every other, with the smallest total cost. Return that cost, or -1 if the villages can't all be connected.
n = 5, roads = [[0, 1, 4], [0, 2, 1], [1, 2, 2], [1, 3, 5], [2, 3, 8], [3, 4, 3]] → 11
1 ≤ n ≤ 100,000 · 0 ≤ roads ≤ 200,000 · 1 ≤ cost ≤ 10,000