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.
It will. Just follow the series. I promise you will get better. And please don’t name call Chandan da. He is also an aspirant of knowledge like you and I. Peace to you!
Hello dardev, thank you very much, for the work that you have done and put together a truely second to none playlist of graph theory please consider making one for dynamic programming as well
