Блог пользователя AshutoshChoudhary

Автор AshutoshChoudhary, история, 9 месяцев назад, По-английски

I was trying to solve the problem, find Euler path / circuit of an undirected graph if it exists

link : https://www.codingninjas.com/studio/problems/euler-path_1214547?leftPanelTabValue=PROBLEM

I was reading this tutorial from cp algorithms,

https://cp-algorithms.com/graph/euler_path.html

where they use adjacency matrix to find the next adjacent node or edge that has not been marked / removed, in the tutorial they mention that we should use adjacency list to store adjacent nodes to achieve time complexity of O(M)

But how will we remove edges in O(1) we can remove an adjacent node v, from the adjacency list of u in O(1) but how to remove u from adjacency list of v, for example if the the current node is u, then to remove an adjacent node we can do v = adjacency_list[u].pop_back()

but now to remove u from the adjacency list of v, we need O(N) time or LogN time if we use set, is there any way to achieve this in O(1) ?

  • Проголосовать: нравится
  • +17
  • Проголосовать: не нравится

»
9 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by AshutoshChoudhary (previous revision, new revision, compare).

»
9 месяцев назад, # |
Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

For each edge in the adjacency list, also store the index of this edge. After using an edge, mark this edge as used in a separate boolean array. If you encounter an edge that is marked as used, you should skip it. This is $$$O(m)$$$ amortized.