Survival algorithm for Network deterministic failures Consider an undirected network $G = (V,E)$ in which edge $e$ $\in$ $E$ fails after (deterministic) time $t(e) &gt; 0$. Network failure occurs at the first instant in which $G$ is no longer connected. Let $m = |E|$ and assume the values $\{t(e): e \in E\}$ are distinct. 

You wish to determine the instant $\tau$ at which the network fails. 

1- Suppose you solve this problem via an intuitive algorithm in which you first sort the edges according to $t(e)$ and then remove the edges, one at a time, to determine if the network has failed. Establish the complexity of this algorithm. 

My Answer: We can sort edges in $O(m\log n)$ time + removing edges takes $O(1)$ * the number of edges to be removed $O(m)$. So the complexity is $O(m^2)$.

2- Show that a variation of your intuitive algorithm from part a can determine $\tau$ in a reduced time complexity in which a factor of m is changed to log m. 

My expectation: I think we might use a heap for storing edges but I am not sure how to implement it.

3- Using what you know about spanning trees, can you write a new algorithm to im­prove upon (or equal) the complexity of your algorithm from part b? (Hint: The network will be failed as soon as every spanning tree. contains a failed edge.)

My expectation: I believe we need to find all spanning trees but I am not sure if this will help reduce complexity.

Can anyone help me solving the given problem or direct me towards a reasonable solution?
Part b
Suppose $t(e_1)&gt;t(e_2)&gt;\cdots$, what you want is $e_i$ such that the graph with $e_1,\ldots,e_i$ is connected. Part a checks the graph with $e_1,\ldots,e_m$, then the graph with $e_1,\ldots,e_{m-1}$, and so on. This process can be improved by binary search, i.e. checking the graph with $e_1,\ldots,e_{m/2}$, then graph with $e_1,\ldots,e_{m/4}$ or with $e_1,\ldots,e_{3m/4}$ depending on the result of the first check, and so on.
Part c
You don't need to check all spanning trees. You only need to find the spanning tree of whose edges the earliest failure time is maximized. This is known as a minimum bottleneck spanning tree (cost of an edge is the negative of its failure time).