Man, please kindly tell me why are you putting the edges after the for loop is completed in dfs function?and then you are reverting the path in the main function…I tried to insert the edges before the for loop in dfs and got Wrong Ans. Do u know why?
CodeChef: Practical coding for everyone -this is my solution that is identical with yours after I consulted yours but only the dfs function is bit different from yours…I want to know why this difference gives Wrong ans…
Thanks in advance
1 Like
Okay i will look at your solution and then tell you.
Thanks Sir
Btw you know why yours is awesome other than the explanation? It’s because i havent found a single resource that outlines this Euler algo on graphs…did you find any? Can you kindly provide the link here?
1 Like
I watched a youtube video to understand eulerian paths -
1.Youtube Video 1 - Click Here
2.Youtube Video 2 - Click here
Watch in sequence.
I also referred to this GFG blog - Click Here
1 Like
I have checked Multiple test cases for this and also applied all brains in it.
I didn’t find a test case in which it gives wrong answer.
Still i am finding the reason why your code fails.
If you got to know the reason, please do tell here.
Thanks for taking out time to go through my code. As you shall see, the only difference between yours code and mine is in the dfs function. So just tell me only this…why are you inserting the edges after the for loop is completed in dfs function…you can straighaway insert the edges before the for loop …in that way you wont need to reverse the path later in the main function…???
1 Like
Yes i am only thinking in the direction in the DFS function.
I am not able to find a difference in My DFS function and your DFS function on the basis of output.
To insert the edges after for loop was not a specific choice. It came naturally.
But i have a reason to it. Putting edges after the for loop means its a tail recursion. In other words, Firstly all the edges will be visited one by one and after the node is reached where there are all visited edges connected to it (and no unvisited edge remaining), it terminates the calls and then edges are filled in the array.
For example,
Let the Order of the call of the nodes was like this : 2-> 3-> 5 -> 6 -> 7
As we know recursion works on a virtual stack.
Stack will be like this :
7 <- Top element
6
5
3
2
When we call node 7, there we encountered no unvisited edges which are connected to 7.
So, the for loop for node 7 ends and corresponding edge is inserted in the array.
After insertion, call for node 7 ends and 7 is popped from the stack.
Now stack is something like this:
6 <- Top element
5
3
2
and the process continues.
and the path array will be filled in the reverse direction , like this: 7,6,5,3,2
In this problem, there will be no edge which will remain unvisited after we found the first node (in our example, it was node 7)which don’t have any unvisited connected edges.
Yes i thought this.
Even If you don’t reverse the function. You will get AC.
See my AC code in which i commented my reverse function - Click Here
Why we got AC?
Answer - Reversed path will also work here because:
Take the case when there will be two nodes with odd degree, then from any of the two nodes you can start the Euler tour.Right?
Take the case when there will be all nodes with even degree, then from any of the nodes you can start the Euler tour.Right?
Hence, there is no particular need to reverse the path.
So basically it does not matter if your DFS is used or my DFS. It should get AC.
and that’s the problem here that i am not able to figure out that why your code is failing.
I guess one reason for the failure is that ,
In my DFS function, Addition of edges are taking place in the call of that particular node.
While in your DFS function, Addition of edges are taking place in the previous call of the particular node.
To understand the above argument,
take the example stated above,
In my DFS function, when for loop ends for node 7 in the call of node 7 , then i added this is in the path array in the same call.
In your DFS function, Addition of the edge corresponding to node 7 is not taking place in the call of 7 ,instead its taking place when you called the previous node(which is 6).Refer the stack if you are confused regarding.
Maybe due to this you are getting WA.
But as i studied this argument, this reason is not affecting the output in any way. In my opinion your solution is correct. But again, I am not able to find a difference in My DFS function and your DFS function on the basis of output.
1 Like
Sir, awesome awesome explanation!!!Thanks very very much to take time out and provide such a clear explanation. You should write a blog about this Euler Path in Codeforces . It will be great for many others…
1 Like
Thanks for the appreciation.
If you got to know the reason why your code actually failed, please do tell here, i also want to know .
This is the basic concept for codeforces community.I will receive downvotes there 
.
No no you shall get upvotes…i guarantee that
1 Like
Thanx for the youtube links. I understand that doing my version of dfs can lead to edges not being discovered in an undirected graph. But ours is a bipartite graph. So, I am actually not convinced whether that situation can ever arise.
1 Like
See, for the computer, graph is just a linked list. Computer does not know whether its a bipartite graph or any other graph. So, dfs should work normally in any case.
I didn’t understand this statement.
What does it mean?Can you elaborate.
I mean in your utube videos(by William Fiset) itself , he has shown what’s the problem with the normal dfs in case of Euler tour. That’s what I am saying…
Your way of finding the starting point for DFS is correct.
William Fiset said that If you do normal DFS (bruteforce) to find out euler tour then its not time efficient.
I know the starting is correct. I said that William Fiset clearly showed that doing dfs in my way will lead to edges remaining to be traversed even if the tour gets completed. See the 2nd video once more, you shall get what I am trying to explain here. But the graph he spoke about was not bipartite. So it is hard to convince myself that such a situation as explained in the video can ever arise in our bipartite graph.
1 Like
I can totally relate to what you are saying and i generated various test cases to test your code but i didn’t find any test case which beats your code. In my opinion, that condition can never arise where some edges are remaining to be visited in your code.
then why its wrong! xD.
Feels like I need to give an open challenge to the codechef community to find the bug in my code. Problem is I don’t have money…
XD
1 Like
Hahaha! xD!
I didn’t understand how the graph as stated in the explanation is achieved following the steps.
The rook is initially present at the position (c,7) but there is no vertex in the right section in the constructed graph which has 7 written on it, or I would say, an edge from c to 7 doesn’t exist in the graph.
How does this work, if we are not considering the edge from c to 7?
1 Like