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

• Can you define what you mean by "find and remove all parallel edges"? It might help to define what you mean by a "parallel edge", and what you mean by removing all of them. – D.W. Feb 12 '18 at 19:13
• How is the graph given to you? – Yuval Filmus Feb 12 '18 at 20:47

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