判断条件
无向图
因为欧拉路径中,起点与终点度数为奇数,其它点的度数均为偶数。
如果是欧拉回路,奇点的个数应该为 0。
有向图
欧拉路径中,最多只有两个点的入度不等于出度。起点出度比入度大 1,终点入度比出度大 1。
如果是欧拉回路,所有点的 入度 = 出度 。
Hierholzer算法
1 | void dfs(int u){ |
ans 逆序存放着遍历的答案。
因为欧拉路径中,起点与终点度数为奇数,其它点的度数均为偶数。
如果是欧拉回路,奇点的个数应该为 0。
欧拉路径中,最多只有两个点的入度不等于出度。起点出度比入度大 1,终点入度比出度大 1。
如果是欧拉回路,所有点的 入度 = 出度 。
1 | void dfs(int u){ |
ans 逆序存放着遍历的答案。