Remove parallel edges in a directed graph in linear time Is there a $O(|V|+|E|)$ algorithm to find and remove all parallel edges in a directed graph? I'm stuck because each idea I've thought of boils down to $deg(v)^2$ comparisons per $v$ which is of course not linear.

Thanks.
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.