For any weighted graph G $=($V$,$ E$,$w$)$ and integer k$,$ define Gk to be the graph that results fromremoving every edge in G having weight k or larger.Given a connected undirected weighted graph G $=($V$,$ E$,$w$),$ where every edge has a uniqueinteger weight, describe an O$(|$E$|$ log $|$E$|)-$time algorithm to determine the largest value of k suchthat Gk is not connected.Solution: Construct an array A containing the $|$E$|$ distinct edge weights in G$,$ and sort it inO$(|$E$|$ log $|$E$|)$ time, e$.$g$.,$ using merge sort. We will binary search to find k$.$ Specifically, consideran edge weight k$0$ in A $($initially the median edge weight$),$ and run a reachability algorithm $($e$.$g$.,$Full$-$BFS or Full$-$DFS$)$ to compute the reachability of an arbitrary vertex x V in O$(|$E$|)$ time.If exactly $|$V $|$ vertices are reachable from x$,$ then Gk$0$ is connected and k $>$ k$0$; recurse on strictlylarger values for k$0.$ Otherwise, Gk$0$ is not connected, so k k$0$; recurse on non$-$strictly smallervalues for k$0.$ By dividing the search range by a constant fraction at each step $($i$.$e$.,$ by alwayschoosing the median index weight of the unsearched space$),$ binary search will terminate afterO$($log $|$E$|)$ steps, identifying the largest value of k such that Gk is not connected. This algorithmtakes O$(|$E$|$ log $|$E$|)$ time to sort, and computes reachability of a vertex in O$(|$E$|)$ time, O$($log $|$E$|)$times$,$ so this algorithm runs in O$(|$E$|$ log $|$E$|)$ time in total.