Question

We just have to find a Euler Circuit in Undirected graph, and i am using heirholzer’s Algorithm but getting TLE in last test case.

Submission

TestCase

Please help me figure out the reason for TLE.

Thanks in advance.!

@vijju123 @ssjgz

The problem with your approach is that whenever you are visiting a edge u r not erasing it.

In the worst case you will try to visit already visited edge in your adjacency list which will consume a lot of time and will result in TLE as happened in last test case.

But i am using visited array on edges, which will make sure that i don’t visit already visited edges.

isn’t that enough?

Not at all

suppose you have k edges which are connected through vertex v.

In each whenever you will visit vertex v you will need O(k) time to traverse it.

If you erase already visited edges then you save upto O(k^2) time as

1+2+3+…k each time you will be skipping 1,2,3,…k edges.

Check out my DFS

```
void dfs(int u)
{
for(idx[u]; idx[u] < g[u].size(); idx[u]++)
{
int v = g[u][idx[u]];
int x = u;
int y = v;
if(x > y)
{
swap(x,y);
}
if(edge[x].find(y) == edge[x].end()) continue;
edge[x].erase(y);
--degree[u];
--degree[v];
dfs(v);
}
stck.push(u);
}
```

See what i did there? I created a global vector idx and did the following to track the edge being currently explored.

```
for(idx[u]; idx[u] < g[u].size(); idx[u]++)
```

When I come back, I don’t start checking ALL neighbours of vertex ‘u’. I simply continue from where I left. Hope that makes sense?

If we don’t take care of this, we will search ALL edges every time in the following case. I am calling this graph a flower-with-petal graph. Only seven petals in this graph, but imagine what happens if there are 10^5 petals (with O(N^2) complexity)

If it doesn’t I am not going to type out more here. I try to make a Eulerian Circuit video on priority and explain this aspect clearly.

Watch out for this video series: https://www.youtube.com/watch?v=BRSTzBEGwyI&list=PL2S6Mj7iLqEjNVq0e-pZ9rSnpAacHzVm3

Let us say a node a k edges.

Your method takes k^2 time for a node.

Now, if you erase erase a edge every time you visit ,this is what happens u erase a edge as u enter the node and erase another edge as u exit the node , thus saving 3/4 th of the time as time taken would be summation (k-1) + (k-3) +(k-5)…which is nearly 4 times efficient.

Yes got it…Thanks!

Thanks for clearing it out…Keep up the good work…!

Yes…Thanks