Remove parallel edges in a directed graph in linear time
Get a list of the edges, this should take no more than $O(|V|+|E|)$ in usual representations. 

Run through the edges and check/add them to adjacency matrix represented as hash-table or sparse array. If an edge's entry has been set you know they are parallel. Do some constant time operations during and after iteration to handle the parallel edges how you'd like.