欧拉迹
欧拉闭迹是指一条包含图中所有边的一条路径，每条边在路径中仅会出现一次，且路径的起点和终点是相同顶点。
一个无向图中包含欧拉闭迹，当且仅当下面两条性质同时满足：
- 图是连通的（不考虑度为$0$的顶点）
- 图中每个顶点的度均为偶数
而一个有向图包含欧拉闭迹，当且仅当下面两条性质同时满足：
- 图是连通的（不考虑度为$0$的顶点）
- 图中每个顶点入度和出度相同
欧拉开迹类似于欧拉闭迹，但是路径的起点和终点允许是不同的顶点。
我们可以发现欧拉开迹可以通过欧拉闭迹删除掉一条边后得到，因此我们也得到了判断欧拉开迹的条件。
一个无向图中包含欧拉开迹，当且仅当下面两条性质同时满足：
- 图是连通的
- 图中除了两个顶点外，其余每个顶点的度均为偶数
而一个有向图包含欧拉开迹，当且仅当下面两条性质同时满足：
- 图是连通的
- 图中除了两个顶点外（这两个顶点如果出度与入度不同，那么必定一个出度比入度少1，一个入度比出度少1），其余每个顶点入度和出度相同
Hierholzer算法用于在连通图寻找欧拉迹，其流程非常简单。
从一个可能的起点出发，进行深度优先搜索，但是每次沿着辅助边从某个顶点移动到另外一个顶点的时候，都需要删除这个辅助边。如果没有可移动的路径，则将所在结点加入到栈中，并返回。
dfs(node, trace){
while(!node.adj.isEmpty()){
Node next = node.adj.removeLast();
dfs(next, trace);
}
trace.addLast(node);
}
最后得到的栈中保存的就是整个欧拉闭迹中的顶点。（要恢复我们需要不断出栈，因此如果你用列表来存欧垃迹的话需要反转一次）。
这里我证明一下算法的正确性。
命题1：如果图满足上面的校验条件，那么Hierholzer算法处理图一定能得到欧拉轨迹。
首先由于图的连通性，因此所有顶点都会被遍历到，故而每条边也都会被正好遍历到一次。同时由于每次返回时才将顶点记录到欧拉迹中，因此顶点之间具有连贯性，即欧拉迹中出现的相邻顶点都对应有一条边独一无二的边存在。结合着两条性质，就可以保证得到的是欧垃迹了。
命题2：如果我们每次都贪心取编号最小的顶点，那么得到的欧拉迹是所有欧拉迹中编号字典序最小的。
由字典序的比较性质可以直接推出结论。
提供一道命题2的应用题目。
题目1：给定长度为$n$的序列$a_0,a_1,\ldots,a_n$。每次我们可以将$a_0$与另外一个元素交换。现在给定目标序列$b_0,\ldots,b_n$，要求将$a$序列通过上述操作转换成$b$序列，问至少需要操作多少次。
首先对于$1\leq i \leq n$，若$a_i\neq b_i$，则我们加入一条有向边$(b_i,a_i)$。现在我们观察从$a_0$出发沿着$m$条有向边组成的某个路径$v_0,v_1,\ldots,v_m$移动，这时候对应于使得$m$个数$v_0,\ldots,v_{m-1}$落在了正确的位置，且此时$a_0=v_m$。如果路径是环路，那么就有$a_0$保持不变。
现在问题变成了，我们要加入一些额外的边，使得图存在欧拉（开或闭）迹，且从欧拉迹中删除所有环后，最后剩下的路径的末尾为$b_0$。
可以发现所有顶点的出度和入度都应该是相等的，除了$a_0$和$b_0$外。如果$a_0=b_0$，则所有顶点的出度和入度都相等，否则$b_0$的入度比出度多$1$，而$a_0$的出度比入度多$1$。很显然不管在哪种情况下$a_0$和$b_0$都在同一个连通块中。
现在考虑不含$a_0,b_0$的连通块，如果连通块中没有边（即只有一个顶点），可以直接忽略。否则我们可以从当前连通块中某个顶点（如果所有顶点入度出度相同，任意选一个，否则选出度小于入度的顶点）连一条边到该连通块中的任意顶点。
重复这个过程，直到所有连通块被处理。可以发现现在图中存在欧拉迹，且用的边最少，且删除环后最后一个顶点为$b_0$。
结果为$E+C-1$，其中$C$表示所有含至少一条边的连通块数目（特殊的$a_0,b_0$所在的连通块也需要被考虑进去），$E$为原图的边数。
提供一道题目。