Finding minimal strongly connected graph
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})$ is strongly connected, so is $G(t)$ where $t$ is the maximum edge weight that is at most $t_{0}$. Thus we can binary search for $t$ over all edge weights.

The algorithm is:


Sort edges by weight. Let $w_{i}$ be the $i$th smallest edge weight (1-indexed). Set $w_{0} = -1$.
Initialise binary search: set $l = 1$ and $h = |E| + 1$
While $l \neq h$:


set $m = \lfloor\frac{l + h}{2}\rfloor$. Then, If $G(w_{m})$ is connected, set $h = m$. Otherwise set $l = m + 1$.

If $l = |E| + 1$, no $t$ works. Otherwise, answer $t = w_{l}$


In the binary search, we maintain the invariant that $G(w_{h})$ is strongly connected (or $h = |E| + 1$), while $G(w_{l - 1})$ is not (assuming $|V| \geq 2$). We exit the loop when $l = h$, thus either $l = |E| + 1$ and the graph is not strongly connected for any $t$, or $G(w_{l})$ is strongly connected, but $G(w_{l-1})$ is not, thus $G(t)$ is not strongly connected for $t &lt; w_{l}$. Thus the algorithm is correct.

The first step takes $\mathcal{O}(E \log E)$ time. The third step takes linear time and is executed at most $\log E$ times. Thus, the complexity is $\mathcal{O}((V + E) \log E) = \mathcal{O}(E \log V)$.