Find the number of SCC of input graph $G$ in $\mathcal{O}(n+m)$, then check whether the number SCC is $1$ or not. If the number of SCC beis $1$ then $G$ is strongly connected. Note that, according your observation $n<m$ we can conclude that $\mathcal{O}(n+m)=\mathcal{O}(m).$