If a library is cheaper than a road, the solution is immediate. Build a library on every node.

def solution(n, library, road, edges): if road >= library: return n * library # ...Otherwise, we want to create a minimum spanning forest, so to minimize the number of roads, keeping track of the number of edges used and how many graphs are actually generated. I found natural using an adapted form of the Kruskal MST (Minimum Spanning Tree) algorithm, that looks very close to our needs.

Kruskal needs a union-find to work, and this ADT is not commonly available out of the box. So, I first implemented a python UnionFind class, see previous post for details.

Then, while working on this problem, I made a slight change to it. My algorithm was simpler and faster if its union() method returned False when nothing was actually done in it, and True only if it led to a join in two existing graph.

Using such refactored UnionFind.union(), I wrote this piece of code based on Kruskal algorithm:

uf = UnionFind(n) road_count = 0 # 1 for edge in edges: if uf.union(edge[0] - 1, edge[1] - 1): # 2 road_count += 1 # 4 if uf.count == 1: # 5 break1. The union-find object keeps track of the numbers of disjointed graphs in the forest, but not of edges. This extra variable does.

2. I need to convert the edges from 1-based to 0-based convention before use them. If the two nodes get connected by this call to union(), I have some extra work to do.

4. An edge has been used by union(), keep track of it.

5. If union() connected all the nodes in a single graph, there is no use in going on looping.

Now it is just a matter of adding the cost for roads and libraries to get the result.

return road_count * road + uf.count * library

Complete python code for problem, union-find, and test case on GitHub.

## No comments:

## Post a Comment