《C++入门到入土》——欧拉回路/欧拉路径
相信大多数人都听说过著名的七桥问题——没听过？那换个通俗的名字：一笔画问题
我们给出一个图（先不考虑有向无向）：
若从一个点开始遍历这个图，每条边都恰好经过一次，那么我们把这条路径称为欧拉路径（该图能够一笔画出）；
若这条路径的起点与终点相同，那么我们称这条路径为欧拉回路。
显而易见，若一条路径是欧拉回路，那么它也一定是欧拉路径。
定义之后，就是该如何判断一个图是否存在欧拉路径了~
首先，我们要看给出的图在看做无向图后是否联通（即各个点之间是否可以两两到达）
若该图在看做无向图后不联通，那么显然不存在欧拉路径
然后定义：
对于无向图的一个节点，其度数等于于其相连的边的数量，可根据其度数分为奇节点（度数为奇数的点）与偶节点（度数为偶数的点）
对于有向图的一个节点，其出度等于以它为起点的边的数量，其入度等于以它为终点的边的数量
再根据图是否无向进行探讨：
该图为无向图：
首先，若图中没有奇节点（全部为偶节点），那么每个节点都存在2k条路径，该点可以通过k条路径向外走，再通过k条路径走回来，显然，这是一个欧拉回路。
并且我们可以看出来，在欧拉回路中，任何一个点都可以作为起点并在遍历一遍后回到该点。
其次，若图中有两个奇节点s,t，我们将这两个奇节点相连后，会发现这两个节点也变成了偶节点，此时与没有奇节点的情况相同，存在一条欧拉回路，以s为起点最后到达t回到s；然后我们再将刚才增加的那条边删去，s与t就不相连了，此时以s为起点，在来到t时无法回到s，于是t就成了这条欧拉路径的终点（s和t可以交换位置）。
总结一下：
无向图欧拉路径：图中恰好存在两个奇节点，这两个度数为奇数的点即为欧拉路径的 起点 s 和 终点 t 。
无向图欧拉回路：图中没有奇节点（所有点的度数都是偶数），起点 s 和终点 t 可以为任意点。
该图为有向图：
若所有的点出度与入度相同（都为k），则一个点可以通过k条边向外走再通过k条边回到该点，明显构成一条欧拉回路。
当图中恰好存在一个点s出度比入度多一，且恰好存在一个点t入度比出度多一时，我们构建一条t到s的有向边，此时情况变成了所有点的出度与入度相同，存在一条欧拉回路从s开始最后到达t回到s；当t到s的这条有向边被去掉后，在最后到达t后无法从t回到s，此时s就成为了这条欧拉路径（因为无法回到起点s）的起点，t为这条欧拉路径的终点（s和t是固定的）。
总结一下：
有向图欧拉路径：图中恰好存在 1 个点出度比入度多 1（这个点即为 起点 s），11 个点入度比出度多 1（这个点即为 终点 t），其余节点出度=入度。
有向图欧拉回路：所有点的入度等于出度（起点 s 和终点 t 可以为任意点）。
在讨论过欧拉回路以及欧拉路径的存在性后，接下来就该考虑代码实现了：
例题：洛谷P7771 【模板】欧拉路径
首先读题，给出的图是有向图，并且要求按照字典序输出，所以我们再输入后要对一个节点所指向的边进行排序；因为我们是用的dfs进行的遍历，所以相对应的节点需要存在一个栈里面，最后倒序输出就是遍历的顺序。
我们首先判断这个图是否有欧拉路径或欧拉回路：
在判断欧拉回路（或欧拉路径）存在后，我们就需要遍历这个图且使其字典序最小了：
最后输出栈内的节点就是路径顺序了：
还有一个要注意的点，就是如果存在欧拉路径的话，s节点是不会初始化的，因此要将s的初始值赋值为1（保证字典序最小）
AC Code：
完结撒西秀园~
祈愿流浪者和心海
