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.

Thanks In Advance.

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.

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.

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.But how it will work for undirected graph? Here we have to delete both u -> v and v -> u edge.

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.

Praise be to Allah! Got it. I thank both of you. :)

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.