Help needed in CSES Graph Problem-Mail Delivery.

№	Пользователь	Рейтинг
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Problem Link.
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

import sys
input = sys.stdin.readline # for fast input...
 
# graph input. n->no of nodes, m->no of edges...
n,m = map(int, input().split())

# constructing bidirectional graph...
# I am using '0' based graph indexing...
graph = [[] for _ in range(n)]
for _ in range(m):
	a,b = map(int, input().split())
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)
 
g = 0 # g is an indicator variable, g->1 means "impossible". 

# degree of each node should be even for Eulerian cycle in undirected graph...
for i in graph:
	if len(i)%2:
		g = 1
		break
if g:
	print("IMPOSSIBLE")
else:
# using stacked method to find Eulerian path to avoid recursion (method link given)...
	stack = [0]
	path = []
	while stack:
		node = stack[-1]
		if len(graph[node]) == 0:
			path.append(node+1)
			stack.pop()
		else:
			nextNode = graph[node][-1]
			graph[nextNode].remove(node)  # I think this is the bottleneck because remove operation is not O(1).
			graph[node].remove(nextNode)
			stack.append(nextNode)
	if len(path) == m+1:
		print(*path)
	else:
		print("IMPOSSIBLE")

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 :)

#include <iostream> #include <vector> #include <set> using namespace std; int m, n; vector<int> res; vector<set<int>> 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 << ' '; }

Комментарии (7)

Показать архивные | Написать комментарий?

snorkel

4 года назад, # |

Change graph to set and it will probably pass. I have solved it using set.

→ Ответить

Danish_amin_01

4 года назад, # ^ |

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-code

import 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.

__Ishmam__

3 года назад, # ^ |

Can u not use dfs to find euler path in an undirected graph? If so, can u pls share the code with me?

navneet.h

Search "thcy github cses solution"

sans-23

2 года назад, # ^ |

Hi, You can find pseudo code here:: https://cp-algorithms.com/graph/euler_path.html#algorithm

senkoustav72

15 месяцев назад, # ^ |

← Rev. 2 →

Pasting a simple CPP implementation for any future reader. Using sets really eased the implementation.

santoshswansi_

5 месяцев назад, # ^ |

Can you tell why this is not working

for(int neigh: set<int>(adjList[node])){ // copy the set since you are erasing after
            adjList[node].erase(neigh);
            adjList[neigh].erase(node);
            dfs(neigh);
        }

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