欧拉路径与欧拉回路

1.定义

欧拉路径：指从某一点出发，走过所有的边一次到达终点。 欧拉回路：是一种特殊的欧拉路径，其起点和终点重合。 # 2.判断有无 ## 第一步：检查图的连通性 方法有：dfs，bfs，并查集 推荐使用dfs，染色法，从每个点出发dfs，记联通块个数 注意，有向图当作无向图来跑。 一个trick：使用vector存无向图时，把边从0开始编号，互为相反边的挨着存，使用时找相反边用原边xor1即可。 ## 第二步：通过度数判断是否存在欧拉路径/欧拉回路 ### 无向图 对于无向图，存在欧拉回路的充分必要条件为：所有点的度数均为偶数。 感性理解一下： 必要性：因为进去多少次就要出来多少次，故必为偶数。 充分性：此时图可看作若干个环组合，而环视一定有欧拉回路的，故整个图有欧拉回路。 存在欧拉路径的充分必要条件为：所有点度数为偶数或仅存在两个点度数为基数，其余点度数为偶数。 因为若在这两点间连一条辅助边，由无向图欧拉回路判定条件，此图必存在欧拉回路，断掉这条边即退化为欧拉路径。 ### 有向图 对于有向图，存在欧拉回路的充分必要条件为：每个点的入度等于出度。 因为有进必有出。 存在欧拉路径的充分必要条件为：最多有一点入度等于出度+1，最多有一点入度等于出度-1，就会有一条从出度大于入度（没有则等于）的点出发，到达出度小于入度（没有则等于）的点的一条欧拉路径。与无向图的欧拉路径一样理解。 # 3.找欧拉路径/欧拉回路 前提条件：已经确定存在欧拉路径/欧拉回路 基本方法：dfs； 欧拉回路可从任意一个点开始dfs，欧拉路径从起点开始，在回溯的时候将边压入结果栈，最后按栈序输出即可。 主要是利用了dfs回溯的性质，不怕走死胡同，会把死胡同留到最后，相当于没有走死。 时间复杂度：O(nm) ### 优化 用一个数组记录每个点搜到了第几条边，然后从这里开始搜。 空间复杂度：O(n+m) # 4.例题 骑马修栅栏（luogu）