By _Muhammad, history, 10 months ago, ,

Assalamualikum!

For finding eular cycle we need to erase edges from graph. But I don't know how to erase edges in O(1) for undirected graph. I can only erase edges in O(log(n)) using C++ set for adjacency list instead of vector.

But I need to erase edges in O(1) so that my eular cycle finding algorithm will run in O(N) instead of O(Nlog(N)). Please tell me how to do it.

• -8

 » 10 months ago, # |   0 All the times that I had to so something like that I always used vectors, and they always performed better than sets, you can try yourself in local. g[i].erase(find(g[i].begin(),g[i].end(),val)); 
•  » » 10 months ago, # ^ |   -8 But time complexity of find() is up to linear in the distance between first and last compares elements until a match is found. So time complexity will be up to O(n^2) in worst case.
 » 10 months ago, # | ← Rev. 2 →   +4 Using set is unnecessary. vector can be thought of as a stack (and you can pop stuff off the stack in amortized O(1)). Just iterate through your adjacency list from back to front.
•  » » 10 months ago, # ^ |   -8 But how it will work for undirected graph? Here we have to delete both u -> v and v -> u edge.
•  » » » 10 months ago, # ^ |   +17 Give every edge an id so u -> v and v -> u have same id. Then if you encounter an edge id you have already encountered, you can pop it without processing it.
•  » » » » 10 months ago, # ^ |   -9 Praise be to Allah! Got it. I thank both of you. :)
 » 10 months ago, # |   0 Just use linked lists or std::list so you can remove edges in $O(1)$ time. I implemented this kind of adjacency list in my solution to Tanya and Password which requires you to find Eulerian path in a directed graph.For undirected graphs, there are ways to setup edges so that each edge contains a pointer to the reverse edge, meaning that when you delete one edge, you can also delete the node containing the reverse edge as well.