Here are my two solutions for ROOKPATH problem
Solution with WA
Solution with AC
The only difference is in line 69. In the former, I pushed the answer first and then called dfs. Aren’t both the same with only the path reversed?
I don’t have much time, so here a quickly made answer. I might expand on it a bit more with visuals later.
For this problem you want to find an Euler tour.
For the AC solution is (quite similar) to Hierholzer’s algorithm. Because you add edges from back to start you explore unused edges along the current path. Adding before the dfs call means an edge can be added that is not connected to the last edge. Suppose the DFS finishes a vertex, then backtracks and explores a new branch. The WA solution has then has the last edge and new branch next to eachother; the AC solution has the last edge of the backtrack and the new branch next to eachother.
1 Like
So the more elaborate answer:
Suppose we have the following graph (after applying the transformation you already found)
4---5
\ /
1---2---3
We start our search at vertex 1. Every time we have multiple choises to continue we take the one with the lowest vertex number.
Let’s start with the WA solution.
We first take 1-2 to get to vertex 2. Then we take 2-3 to go to vertex 3. Now we are stuck so we backtrack. Next we take 2-4 to reach vertex 4. After that 4-5 to reach vertex 5 and finally 5-2 to reach vertex 2 again. We are once again stuck and backtrack to where we started. The sequence of edges produced becomes: 1-2,2-3,2-4,4-5,5-2; but the edge 2-3 doesn’t attach to the next edge 2-4.
Now look at the AC solution.
We first use edge 1-2 to reach vertex 2. Then we use edge 2-3 to reach vertex 3 and then we are stuck. We backtrack, and store the last edge 3-2 at that point. We next choose 2-4,4-5,5-2 and we are stuck again. Then when backtracking we add the edges 2-5,5-4,4-2,2-1 and we are done. Notice that the entire sequence 3-2,2-5,5-4,4-2,2-1 does form a path.
Why then does the AC solution not break? In the graph there are at most two odd degree vertices at all times. The first one of them is where the DFS currently is, the other is always at the end of the path we made in ans. We only add edges to ans when we are stuck; so the end of the DFS is in a degree 0, even, vertex. This can only happen when the end of the DFS path and the end of the ans path are at the same vertex, so the new edge actually extends the path. Each edge used by the DFS will at some point be added to ans when backtracking; and the DFS will visit each edge, so at the end ans contains all edges and forms a proper path.
In short, it isn’t “just the path in reverse” because that ignores the branching of the DFS.
2 Likes
I got the point. Thank you for the explanation.