### Danish_amin_01's blog

By Danish_amin_01, history, 4 years 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

| Write comment?
 » 4 years ago, # |   +4 Change graph to set and it will probably pass. I have solved it using set.
•  » » 4 years 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.
•  » » » 3 years 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?
•  » » » » 3 years ago, # ^ |   0 Search "thcy github cses solution"
•  » » » » 21 month(s) ago, # ^ |   0 Hi, You can find pseudo code here:: https://cp-algorithms.com/graph/euler_path.html#algorithm
•  » » » 11 months ago, # ^ | ← Rev. 2 →   0 Pasting a simple CPP implementation for any future reader. Using sets really eased the implementation. #include #include #include using namespace std; int m, n; vector res; vector> adj; // euler circuit void dfs(int curr) { auto &edges = adj[curr]; while(!edges.empty()) { auto edge = *edges.begin(); edges.erase(edge); adj[edge].erase(curr); dfs(edge); } res.push_back(curr); } int main() { cin >> n >> m; adj.resize(n + 1); for (int i = 1; i <= m; ++i) { int x, y; cin >> x >> y; adj[x].insert(y); adj[y].insert(x); } for (int i = 1; i <= n; ++i) { if (adj[i].size() % 2) { cout << "IMPOSSIBLE\n"; return 0; } } dfs(1); if (res.size() != m + 1) { cout << "IMPOSSIBLE\n"; return 0; } for (auto &r : res) cout << r << ' '; } 
•  » » » » 5 days ago, # ^ |   0 .ComplaintFrame { display: inline-block; position: absolute; top: 0; right: -1.4em; } .ComplaintFrame a { text-decoration: none; color: #ff8c00; opacity: 0.5; } .ComplaintFrame a:hover { opacity: 1; } ._ComplaintFrame_popup p, ._ComplaintFrame_popup button { margin-top: 1rem; } ._ComplaintFrame_popup input[type=submit] { padding: 0.25rem 2rem; } ._ComplaintFrame_popup ul { margin-top: 1em !important; margin-bottom: 1em !important; } Can you tell why this is not working for(int neigh: set(adjList[node])){ // copy the set since you are erasing after adjList[node].erase(neigh); adjList[neigh].erase(node); dfs(neigh); }