The chief engineer is in charge of deciding the mountainous road-network that will be kept open (cleared of debris and maintaine
d regularly) during the winter months. Each road connects different small towns in the mountains, and all towns are connected to each other either directly or indirectly. Each road is associated with a value indicating the level of danger in maintaining that road during winter months. There are many subsets of roads such that the roads in such subsets keep the towns connected directly or indirectly. Each subset is assigned a cost of maintenance, which is directly proportional to the highest danger level of the road present in that subset. The engineer wants to select the smallest subset that keeps the towns connected directly or indirectly and that also has the lowest cost of maintenance. Develop an algorithm to find such a subset. Justify the correctness of your algorithm and derive its runtime.
