_Muhammad's blog

By _Muhammad, history, 4 weeks ago, In English,

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.

 
 
 
 
  • Vote: I like it
  • -8
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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));
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    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.

»
4 weeks ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    But how it will work for undirected graph? Here we have to delete both u -> v and v -> u edge.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      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.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it -9 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.