GATE Computer Science (CS) 2020 Solved Papers

Let $\mathit{G}=\left(\mathit{V},\mathit{E}\right)$ be a weighted undirected graph and let $\mathit{T}$ be a Minimum Spanning Tree (MST) of G maintained using adjacency lists. Suppose a new weighted edge $\left(\mathit{u},\mathit{v}\right)\in \mathit{V}\times \mathit{V}$ is added to $\mathit{G}$. The worst case time complexity determining if $\mathit{T}$ is still an MST of the resultant graph is