这是一道典型的DFS的题目。但是有两种不同的思路。
方法一：
相对直观的DFS的思路是：从起点出发，按字典顺序尝试每一个可以抵达的下一节点进行深度搜索，直至走到尽头。如果走到尽头的时候满足终止条件，即所有的机票都已经恰使用一次，那么就说明搜索成功了。否则，需要回溯到上一级搜索其他支线。
这个方法有一个缺点。在本题中，题目保证最后的路径一定会使用到所有的机票。这就说明，如果尝试某一条支路的过程中走到了底没有成功（也就是说走到底的时候并没有用完所有的机票），虽然暂时失败了，但这条支路肯定会在之后的搜索中再走一遍（因为最终走成功路径一定会包括所有的机票）。这样，我们发现，这前一次没有成功的搜索其实被白白浪费了：明知道之后肯定会再走，但却没有带来任何帮助，效率低下。
方法二：
这题本质就是一个欧拉一笔画的问题。现在来回顾几个概念：
欧拉路径：从一个点出发，到达另外一个点，所有的边都经过且只经过1次。
欧拉回路：欧拉路径中，终点能回到起点。
如果判断是否存在欧拉路径？
1.无向图：如果只有两个点的度是奇数，其他的点的度都是偶数，则存在从一个奇数度点到另一个奇数度点的欧拉路径。如果所有的点的度都是偶数，那么就是欧拉环路。
2.有向图：所有的点的入度等于出度，那么就存在欧拉回路。如果最多有一个点出度大于入度by1，且最多有一个点入度大于出度by1，那么就有一条从前者（如果没有则可以任意）到后者（如果没有则可以任意）的欧拉路径。
因为本题保证了是一条欧拉路径，那么我们可以这么考虑。对于A点，它有B点和C点两个下家，这说明什么呢？假设其中一个B点是能够一次性做到终点目的地的标准欧拉路径，那么我们就放心地继续DFS(B)就可以了；那么走另外一个C点会有什么结果呢？那就是之后一定会重新会到A点让你可以继续走B点分支，因为本题的性质保证了会存在A->C->A的环。所以在第二种情况下，你依然可以放心地去DFS(C)。
所以说，你遇到A，可以按任意顺序DFS下家，因为总是会回来的。但是要注意的是，等你恰好遍历A的所有下家路径时，这说明A就是一个分界点，A的上游是整个欧拉路径的前半部分，A的下游是整个欧拉路径的后半部分，所以你把A放进整个path里。此时path已有的部分，是整个欧拉路径的后半部分，是你在之前递归的过程中已经填充好了的；而整个欧拉路径的前半部分，则会在之后待填充。
所以，在具体的代码中，我们每尝试一个A的下家之前，会断开A和这个下家之间的通路。这样，如果访问到A没有下家了，说明A是当前的终端了（除去所有已经确定的欧拉路径的后半部分），就将A加入path。
另外，注意到我们填充path的顺序其实是按照从后往前来的，所以最终要将path逆序返回。
另外，在同一层级的搜索中，我们依然是会优先考察字典序小的目的地。所以，对于A的下家，其实我们是按字母倒序尝试。