There is a fast algorithm for this problem: (assuming you meant that $S$ is the set of edges being removed from $G$)
- Compute the strongly connected components of $G$, with an algorithm of your choice. For example, this DFS-based algorithm can work in $O(|V|+|E|)$.
- Define $S$ to be the set of edges between any two strongly connected components.
This algorithm is very efficient, running in linear time with respect to $|V|$ and $|E|$.
Additionally, it computes a correct set (which is easy to see why) and this set is the minimal set.
Indeed, if there is an edge $(v,u)$ that is between two strongly connected components, but it is not in $S$, then $(v,u)$ will be in the new graph. Notice there is no path $u\rightsquigarrow v$ (otherwise $v$ and $u$ would have been in the same strongly connected component) and hence, the new graph will contain a component that is not strongly connected.