欧拉路径/欧拉回路/欧拉图/欧拉图的判定/欧拉路径的构造

接下来所有的都是基于一张联通的图\(G\)来讨论的，其点集为\(V\)，边集为\(E\)。

欧拉路径：从一个顶点开始能经过所有边恰好一次的路径；欧拉回路：能够恰好回到起始点的欧拉路径；欧拉图：存在欧拉回路的图，存在欧拉路径但不存在欧拉回路的图也叫做半欧拉图。
欧拉图的性质：

1. 存在欧拉路径
2. 每个点的度数都是偶数（有向图中，这个性质为入度等于出度）
3. 能够分成若干个边集不交的回路

可以证明上述三个条件是等价的，也就是都是欧拉图存在的充要条件。
\(1\Rightarrow 2\)，一个点如果通过一个边出去，那么他一定会通过另一个边再回来，并且欧拉回路的路径不交，所以通过他出去的边数就是进入他的边数，所以他的度数就是偶数了（或入度等于出度）
\(2\Rightarrow 3\)，考虑从一个点\(u\)出发，选择一个与\(u\)相邻的点\(v\)，走到\(v\)，并删除\((u,v)\)这条边，这时，\(u,v\)的度数都是奇数，意味着\(v\)还有出边还能继续走，并且下一步以后\(v\)的度数就变成偶数了。也就是说，当且仅当走回\(u\)之后这个操作才可能停止，又因为图的边数是一定的，所以一定会终止，也就一定能走到\(u\)点。而找到这个回路以后，图依然满足\(2\)性质，所以还能继续划分回路知道没有边
\(3\Rightarrow 1\)，考虑，如果有两个边不交但是有点相交的回路，那么就可以通过这个交点把两个回路合并成为一个回路。那么考虑，是否可以把所有回路都合并到一起。我们证明，任意两个回路都能够合并起来。取出两个回路\(P_1,P_2\)，若\(P_1,P_2\)有交点，则直接合并，如果没有交点，取出\(u\in V(P_1),v\in V(P_2)\)，因为\(G\)联通，所以必定存在一条从\(u\)到\(v\)的路径\(u\to e_1\to e_2\dots e_k\to v\)，并且\(e_i\in E(C_i)\),\(e_i\)表示一条边,\(C_i\)表示\(e_i\)属于的一个回路，那么\(P1\text{与}C_1,C_i\text{与}C_{i+1},C_{k}\text{与}P_2\)就一定存在交点，那么就可以通过这个交点进行合并了。所以所有的回路一定能够合并成一个欧拉回路了。

欧拉图的判定：使用上述三个性质即可。

欧拉路径的构造：
构造是基于上面的第\(3\)个性质来构造的，就是从一个点开始，先找到一个回路，然后再在回路上枚举交点，通过这个交点合并其他的回路，使用链表写会比较方便。当然自己写的比较丑。

    tot ++;trans[tot] = 0;// 链表起点
    nxt[tot] = tot + 1;tot ++;trans[tot] = to;// 手动加入第一个点
    E = tot;// 终点
    cur = 1;// 当前在的点
    lst = 1;// 上一个点
    while(cur != E) {
        while(!e[trans[cur]].count() && cur != E) {
            lst = cur;cur = nxt[cur];
        }
        if(!e[trans[cur]].count()) break;
        tot ++;trans[tot] = trans[cur];
        int tmp = nxt[lst];
        nxt[lst] = tot;
        flag = false;
        dfs(tot, trans[tot], tmp, n);// 寻找新的回路
        cur = nxt[lst];
    }