欧拉路径+欧拉回路

• 关键求解法（有向图或无向图，求解欧拉路径或欧拉回路都适用）

  • 从起点开始遍历，
    • 当遍历到 \(u\) 时，若有 \(u -> v\) 则删掉 \(u->v\) 这条边后，继续 dfs \(v\)
    • 当 \(u\) 没边了后，将 \(u\) 入栈
    • 最后依次输出栈顶元素。
  • 会发现当一个点的所有出边都被搜索完之后，才会被入栈，这样，在栈中的点是无法继续往外走的，而栈外的点才可以往外走。所以，栈外的点在欧拉路径中的位置是在栈内的点之前的，否则，如果先走栈内的点，一些只有栈外的点可以到达而栈内的点无法到达的点是不会被走到的，这样就不能经过所有的边的，不符合要求。所以，当一个点的全部出边都经过之后，表示这一个点不能再到达其他点，为了可以到达其他点，只能让这个点位于其他点之后，所以要入栈。