1

We can solve the problem in $\mathcal{O}(E \log V)$ by binary search. We can identify the strongly connected components in a graph in linear ($\mathcal{O}(V + E)$) time. Thus we can check if the graph is strongly connected in linear time. If $G(t_{0}) = (V, E(t_{0}))$ is strongly connected, so is $G(t) = (V, E(t))$ for $t \geq t_{0}$. Further, if $G(t_{0})$...


1

We call an edge superheavy if it is the unique heaviest edge in some cycle. This post shows that an edge $e\in A$ if and only if $e$ is not superheavy. To find all edges that are not superheavy, we can first sort the edges according to their weights from small to large. Then, we remove all edges, re-add them in this order, and track the connected ...


Only top voted, non community-wiki answers of a minimum length are eligible