欧拉迹
欧拉闭迹是指一条包含图中所有边的一条路径，每条边在路径中仅会出现一次，且路径的起点和终点是相同顶点。
一个无向图中包含欧拉闭迹，当且仅当下面两条性质同时满足：
- 图是连通的（不考虑度为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的序列a0,a1,…,an。每次我们可以将a0与另外一个元素交换。现在给定目标序列b0,…,bn，要求将a序列通过上述操作转换成b序列，问至少需要操作多少次。
首先对于1≤i≤n，若ai≠bi，则我们加入一条有向边(bi,ai)。现在我们观察从a0出发沿着m条有向边组成的某个路径v0,v1,…,vm移动，这时候对应于使得m个数v0,…,vm−1落在了正确的位置，且此时a0=vm。如果路径是环路，那么就有a0保持不变。
现在问题变成了，我们要加入一些额外的边，使得图存在欧拉（开或闭）迹，且从欧拉迹中删除所有环后，最后剩下的路径的末尾为b0。
可以发现所有顶点的出度和入度都应该是相等的，除了a0和b0外。如果a0=b0，则所有顶点的出度和入度都相等，否则b0的入度比出度多1，而a0的出度比入度多1。很显然不管在哪种情况下a0和b0都在同一个连通块中。
现在考虑不含a0,b0的连通块，如果连通块中没有边（即只有一个顶点），可以直接忽略。否则我们可以从当前连通块中某个顶点（如果所有顶点入度出度相同，任意选一个，否则选出度小于入度的顶点）连一条边到该连通块中的任意顶点。
重复这个过程，直到所有连通块被处理。可以发现现在图中存在欧拉迹，且用的边最少，且删除环后最后一个顶点为b0。
结果为E+C−1，其中C表示所有含至少一条边的连通块数目（特殊的a0,b0所在的连通块也需要被考虑进去），E为原图的边数。
提供一道题目。