How to remove cycles from a directed graph by edge contraction?
Since the only way to get rid of a cycle by edge contractions is to contract all the edges of the cycle to result in a single vertex, the vertices of the new graph are the strongly connected components of the original graph. Two vertices have an edge between them if the original components corresponding to these two vertices had such an edge in the same direction.

Strongly connected components can ve found in linear time.