The Muddy City consists of n houses but no proper streets; instead, the different houses are connected to each other via m bidirectional muddy roads. The newly elected mayor of the city aims to pave some of these roads to ease the travel inside the city but also does not want to spend too much money on this project, as paving each road e between houses u and v has a certain cost ce (different across the muddy roads). The mayor thus specifies two conditions: • Enough streets must be paved so that everyone can travel from any house to another one using only the paved roads (you may assume that this is always possible);
• The paving should cost as little as possible.
You are chosen to help the mayor in this endeavor.
(a) Design and analyze an O(m log m) time algorithm for this problem. (10 points)
(b) The mayor of a neighboring city is feeling particularly generous and has made the following offer to Muddy City: they have identified a list of O(log m) different muddy roads in the city and are willing to entirely pay the cost of paving exactly one of them (in exchange for calling the new street after the neighboring city).
Design and analyze an O(m log m) time algorithm that identifies the paving of which of these roads, if any, the mayor should delegate to the neighboring city to further minimize the total cost-note that if you decide to pave one of the roads payed by the neighboring city, you only need to pay a cost of 1 (for making a plaque of the name of the street). (15 points)
Hint: Design an algorithm that given a MST T of a graph G, and a single edge e, in only O(m) time finds an MST T' for the graph G' obtained by changing the weight of the edge e to 1.