### Danish_amin_01's blog

By Danish_amin_01, history, 21 month(s) ago,

I am facing Time Limit Exceed in this problem and I am not able to improve my code any further.
(The following code is in python, but I have even tried in same thing in C++ and got TLE for last test case.)

My Code

I have implemented the method from this Link of CP-Algorithms in my code.
Please read my code. I have mentioned what could be the bottleneck in my code, and I don't know how to overcome this problem. If I avoid removing edges from graph, then how should I track what edges not to visit.
Thanks in advance and If you want to help and don't understand what my problem is or anything else just comment for the same I would try to explain better what is my issue here.
Also you can simply comment some links or similar problems related to this so that I can do some further research.
Any kind of help is acceptable :)

• +13

 » 21 month(s) ago, # |   +4 Change graph to set and it will probably pass. I have solved it using set.
•  » » 21 month(s) ago, # ^ |   +3 Thanks a lot buddy, I don't know why it didn't strike me to use sets. Anyways I am attaching my accepted code for those people who may stumble here in future for the same problem. AC-codeimport sys; input = sys.stdin.readline n,m = map(int, input().split()) graph = [set() for _ in range(n)] # using set for faster deletions of elements... for _ in range(m): a,b = map(int, input().split()) graph[a-1].add(b-1) graph[b-1].add(a-1) g = 0 for i in graph: if len(i)%2: g = 1 break if g: print("IMPOSSIBLE") else: stack = [0] path = [] while stack: node = stack[-1] if len(graph[node]) == 0: path.append(node+1) stack.pop() else: nn = graph[node].pop() # here it makes difference... graph[nn].remove(node) stack.append(nn) if len(path) == m+1: print(*path) else: print("IMPOSSIBLE") I recommend to try with sets if not considered, before looking at code.
•  » » » 12 months ago, # ^ |   0 Can u not use dfs to find euler path in an undirected graph? If so, can u pls share the code with me?
•  » » » » 12 months ago, # ^ |   0 Search "thcy github cses solution"
•  » » » » 12 months ago, # ^ |   0 I used dfs. Here is my implementation using Hierholzer's Algorithm
•  » » » » » 12 months ago, # ^ |   0 Thanks a lot, bro.
•  » » » » » 7 weeks ago, # ^ |   0 THANKS