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.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
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.
Assuming you mean a directed multigraph...
You can visit each vertex using a depth-first search with edge duplicate detection with a hash table (to avoid infinite cycles). If no cycles, each node gets visited exactly once ~ |V|. If there are cycles, one of the nodes in the cycle may be visited twice ~ <|V|. |V|+<|V|=O(|V|).
In the traversal, if an edge is already in the hash table, delete it (it is a duplicate), otherwise, traverse it and add it to the hash table. There will be exactly |E| duplicate checks and <=|E| traversals. A hash table lookup is O(1) so you get O(|V|+|E|).