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_lsiist[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) ?
↵
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
↵
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) ?
