欧拉路

1 基础概念

• 欧拉回路：每条边只经过一次，而且回到起点
• 欧拉路径：每条边只经过一次，不要求回到起点
• 欧拉回路判断：
  • 无向图：连通(不考虑度为 0 的点)，没有奇度顶点
  • 有向图：强连通，每个顶点出度等于入度
  • 混合图(有无向边和有向边)：首先是基图连通(不考虑度为 0 的点)，然后需要借助网络流判定。
    1. 首先给原图中的每条无向边随便指定一个方向（称为初始定向），将原图改为有向图 G’，然后的任务就是改变 G’ 中某些边的方向（当然是无向边转化来的，原混合图中的有向边不能动）使其满足每个点的入度等于出度。
    2. 设 $D[i]$ 为 G’ 中 (点 $i$ 的出度 - 点 $i $的入度）。可以发现，在改变 G’ 中边的方向的过程中，任何点的 $D$ 值的奇偶性都不会发生改变（设将边 $<i, j>$ 改为 $<j, i>$，则 $i 入度加 1 出度减 1，j$ 入度减 1 出度加 1，两者之差加 2 或减 2，奇偶性不变）！而最终要求的是每个点的入度等于出度，即每个点的 $D$ 值都为 0，是偶数，故可得：若初始定向得到的 G’ 中任意一个点的$D$值是奇数，那么原图中一定不存在欧拉环！
    3. 若初始 $D$ 值都是偶数，则将 G’ 改装成网络：设立源点 $S$ 和汇点 $T$，对于每个 $D[i]>0$ 的点$i$，连边 $<S, i>$，容量为 $D[i]/2$；对于每个 $D[j]<0$ 的点 $j$，连边 $<j, T>$，容量为 $-D[j]/2$； G’中的每条边在网络中仍保留，容量为 1（表示该边最多只能被改变方向一次）。求这个网络的最大流，若 $S$ 引出的所有边均满流，则原混合图是欧拉图，将网络中所有流量为 1 的中间边（就是不与 $S$ 或 $T$关联的边）在 G’ 中改变方向，形成的新图 G” 一定是有向欧拉图；若 $S$ 引出的边中有的没有满流，则原混合图不是欧拉图。
• 欧拉路径的判断：
  • 无向图：连通(不考虑度为 0 的点)，没有奇度顶点或恰有两个奇度顶点
  • 有向图：基图连通(把边当成无向边，同样不考虑度为 0 的点)，每个顶点出度等于入度或
    者有且仅有一个点的出度比入度多 1，有且仅有一个点的出度比入度少 1，其余出度等于入
    度。
  • 混合图：如果存在欧拉回路，一定存在欧拉路径了。否则如果有且仅有两个点的（出度 -入
    度）是奇数，那么给这个两个点加边，判断是否存在欧拉回路。

https://blog.csdn.net/richenyunqi/article/details/80382450/

欧拉路径模板

1 递归

//无向图的欧拉路径
#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e4+5;
vector<int>graph[maxn],path;//图、欧拉路径的倒序
int N, M;//顶点数、边数
bool visit[maxn][maxn];//表示边是否已被访问
//顶点v的度数是否为奇数
bool f(vector<int>&v){
    return v.size()%2==1;
}
//深度优先遍历
void DFS(int v){
    for(int i=0;i<graph[v].size();++i){//遍历该点能到达的结点
        int w=graph[v][i];
        if(!visit[v][w]){//该边没有被访问过
            visit[v][w]=visit[w][v]=true;//该边已被访问
            DFS(w);//递归遍历
        }
    }
    path.push_back(v);//加入欧拉路径中
}
int main(){
    scanf("%d%d",&N,&M);//输入点数、边数
    for(int i=0;i<M;++i){//输入边，无向图
        int a,b;
        scanf("%d%d",&a,&b);
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    for(int i=1;i<=N;++i)//排序、题目要求输出字典序最小的一种方案
        sort(graph[i].begin(),graph[i].end());
    DFS(1);
    int k=count_if(graph+1,graph+N+1,f);//度数为奇数的顶点个数
    //连通、没有奇度顶点或恰有两个奇度顶点且起点为奇度顶点
    if(path.size()==M+1&&(k==0||(k==2&&f(graph[1]))))
        for(int i=path.size()-1;i>=0;--i)//反向输出路径
            printf("%d ",path[i]);
    else
        printf("-1");
    return 0;
}

2 非递归

//无向图的欧拉路径
#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e4+5;
vector<int>graph[maxn],path;//图、欧拉路径的倒序
int N, M;//顶点数、边数
bool visit[maxn][maxn];//表示边是否已被访问
//顶点v的度数是否为奇数
bool f(vector<int>&v){
    return v.size()%2==1;
}
int main(){
    scanf("%d%d",&N,&M);//输入点数、边数
    for(int i=0;i<M;++i){//输入边，无向图
        int a,b;
        scanf("%d%d",&a,&b);
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    for(int i=1;i<=N;++i)//排序、题目要求输出字典序最小的一种方案
        sort(graph[i].begin(),graph[i].end());
    stack<int>s;
    s.push(1);//1号顶点(起点)入栈
    while(!s.empty()){
        int v=s.top(),i;
        for(i=0;i<graph[v].size();++i){//遍历该点能到达的结点
            int w=graph[v][i];
            if(!visit[v][w]){//该边没有被访问过
                s.push(w);//顶点w入栈
                visit[v][w]=visit[w][v]=true;//该边已被访问
                break;//跳出循环
            }
        }
        if(i==graph[v].size()){//没有还未访问的边
            path.push_back(v);//顶点v加入欧拉序列
            s.pop();//出栈
        }
    }
    int k=count_if(graph+1,graph+N+1,f);//度数为奇数的顶点个数
    //连通、没有奇度顶点或恰有两个奇度顶点且起点为奇度顶点
    if(path.size()==M+1&&(k==0||(k==2&&f(graph[1]))))
        for(auto i=path.rbegin();i!=path.rend();++i)//倒序输出
            printf("%d ",*i);
    else
        printf("-1");
    return 0;
}