Consider the following variant of the Minimum Spanning Tree $($MST$)$ problem. We

are given an undirected graph G $=($V$,$ E$)$ with n vertices $($numbered from $0$ to

n $1)$ and m edges, a positive $($not necessarily unique$)$ edge cost ce for each edge

in E$,$ and a subset of edges A $$ E $($note that A may contain cycles$).$ Suppose that E

represents a set of possible direct fibre links between vertices and A represents the

existing set of direct fibre links between vertices. We would like to find the cheapest

way to connect all the vertices into one connected network.

The abstract problem we are interested in solving is to find a subset X $$ E $\backslash$ A

of edges of minimum cost such that $($V$,$ X $\backslash$cup A$)$ is connected.

Task: Design an algorithm that solves this problem in O$($m log n$)$ time.

Implement your algorithm $($in Ed$)$ and test it on the following instances: Graph$8,$

Graph$250,$ Graph$1000.$ Each instance is given in a text file as described in Question

$1.$

Each graph instance is given in a text file using the following format $($where a is

the number of edges in A$)$:

n

m

vertexId vertexId weight

vertexId vertexId weight

$...$

a

vertexId vertexId

vertexId vertexId

$...$

For example, the following text describes the instance depicted in Fig. $2.$ Note

that the vertices are numbered from $0$ to n $1.$

$4$

$5$

$022$

$016$

$035$

$138$

$2$

comp$2123$ Assignment $4$ S$12024$

$233$

$2$

$02$

$13$

Your program should read input from a text file, and calculate the cost of the

solution generated by your algorithm, that is$,$ the cost of the edges in X $\backslash$cup A$.$ Your

program does not need to return the actual edges, just print out the total cost

rounded to two decimal places to standard output.

Your code will not be benchmarked or tested for time complexity, but for full

points it must be able to run instances similar to "Graph$1000",$ and each test will

time out after $5$ seconds.

Below is the scaffold

# Read in the number of vertices $($n$)$ and edges $($m$)$

n $=$ int$($input$())$

m $=$ int$($input$())$

# Read the edges from stdin.

edges $=[]$

for $\_$ in range$($m$)$:

edges.append$($input$().$split$())$

# Read the A edges. You may want to use a different data$-$structure.

n$\_$A$,$ A $=$ int$($input$()),[]$

for $\_$ in range$($n$\_$A$)$:

A$.$append$($input$().$split$())$

mst$\_$weight $=0.$

# Print the weight of the mst to two decimal$-$places.

print$(\text{'}\{$:$\mathrm{.}2$f$\}\text{'}.$format$($mst$\_$weight$))$