Euler path of undirected graph in O(M)
Разница между en1 и en2, 4 символ(ов) изменены
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_l
siist[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)
 ?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский AshutoshChoudhary 2024-02-23 03:31:04 4 Tiny change: 'djacency_lsit[u].pop_b' -> 'djacency_list[u].pop_b' (published)
en1 Английский AshutoshChoudhary 2024-02-23 03:29:23 983 Initial revision (saved to drafts)