定义
通路：一条从(v_i)到(v_j)的不经过重复边的一条路经，长度为通路中边的个数
回路：起点和终点相同的通路
欧拉通路：经过图(G)所有边一次的通路
欧拉回路：经过图(G)所有边一次的回路
欧拉图（(E)图）：具有欧拉回路的图
半欧拉图：具有欧拉通路但不具有欧拉回路的图
平凡图：只有一个节点的图
判定
无向图：(G)为连通图，有且仅有两个奇数度顶点，则图存在欧拉通路，无奇数度节点，则图存在欧拉回路
有向图：(G)为连通图，起点出度比入度大(1)，终点入度比出度大(1)，则存在欧拉通路，所有顶点入度等于出度，则存在欧拉回路
证明： 无向图(G)为连通图，无奇数度节点，则图存在欧拉回路
必要性显然
充分性：
由于所有节点都是偶数度节点，那么必然存在一个简单环，如果这个环就是欧拉回路结论已经成立，否则删掉该环上所有边，子图中的节点一定不存在奇数度节点
由于图的连通性，子图与该环必定有公共顶点，以公共顶点为起点在子图中寻找简单环递归做
又因为子图中的环与原图简单环有公共顶点，所以二者可以并在一起，最终形成欧拉回路
证明： 无向图(G)为连通图，有且仅有两个奇数度顶点，则图存在欧拉通路
必要性显然
充分性：
将两个奇数度顶点直接连边，图(G)中必定存在欧拉回路
有向图同理
定理
1.一个非平凡联通图是欧拉图当且仅当它每条边属于奇数个环
证明：几个环交接处的边的两个顶点的度数为环数+1
实现
判断图中存在欧拉路或欧拉回路后，只要选择正确的起点无脑递归，无路可走就回溯，回溯时记录路径
inline void dfs(int now)
{
for(int i=l;i<=r;++i)
{
if(g[now][i])
{
--g[now][i];
--g[i][now];
dfs(i);
}
}
ret[++sum]=now;
}
最后将路径倒序输出
while(sum) printf("%d
",ret[sum--]);
为什么一定要倒序输出不是直接输出？
考虑以下情况（无向图）：
标准(dfs)很可能(1)之后进入(2)，转了一圈之后发现无法返回，那么我们(dfs)树上的顺序很可能是：
(1、2、3、4、2、5、6、1)
但这很明显不是欧拉路的顺序
若我们用栈，在回溯时将节点入栈，先将(2、4、3、2、1)压入栈底
而后将(6、5、1)进栈
那么倒序输出的顺序就是(1、5、6、1、2、3、4、2)
也就是说在求欧拉通路时，死路一定要走的但不能放在最早走，而是一旦遇到通过栈在走完回路之后通过