图的欧拉道路与回路（不重复的走过所有边而不是点）
：
定理1：存在欧拉路的条件：图是连通的，有且只有2个奇点。
定理2：存在欧拉回路的条件：图是连通的，有0个奇点。
前提必须连通
并且是无向图
对于有向图，有：
图是联通的（忽略边的方向）
当所有节点入度等于出度时存在欧拉回路
当只有一个节点出度等于入度+1，且只有一个节点入度等于出度+1时且其它节点入度等于出度时存在欧拉道路
此时出度等于入度+1的为起点，入度等于出度+1的为终点
不确定！！
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int degreeru[201],degreechu[201],vis[201][201],g[201][201];
int n,m;
void dfs(int u){cout<<u<<" ";for(int i=1;i<=n;++i){if(g[u][i]&&!vis[u][i]){vis[u][i]=1;//注意有向图！！！ dfs(i);}}}
int main(){//有向图 cin>>n>>m;for(int i=0;i<m;++i){int u,v;cin>>u>>v;g[u][v]=1;++degreechu[u];//分入度出度！！ ++degreeru[v];}int t=0;int a,fl=0;for(int i=1;i<=n;++i){if(degreechu[i]==degreeru[i]+1){++t;if(t>1){cout<<"No"<<endl;return 0;}a=i;}else if(degreechu[i]!=degreeru[i]){fl=1;}}if(t==0&&fl){cout<<"No"<<endl;return 0;}else if(t==0){a=1;cout<<"Hui"<<endl;}else if(t==1){cout<<"Dao"<<endl;}dfs(a);cout<<endl;return 0;}
时间复杂度都是O(n+e)
求解欧拉道路的代码，洛谷P7771
问题在于欧拉道路可能有好几个环拼起来加一段道路，所以说乱走可能走到死胡同没法回退到环，所以说不能随便dfs，需要一些技巧
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>using namespace std;
#define ll long long
#define re register
int n,m;int heads[100006],nexts[400006];
int tos[400006];
//int oth[400006];
int nums=0;
bool vis[400006];
vector<int>g[100006];
int indeg[100006],oudeg[100006];
inline void adds(int u,int v){tos[++nums]=v;nexts[nums]=heads[u];heads[u]=nums;
}
int tt=0;
int ans[300006];
inline void dfs(int u){int las=0;for(int i=heads[u];i!=0;i=nexts[i]){if(vis[i]){if(i==heads[u]){heads[u]=nexts[i];continue;}nexts[las]=nexts[i];}else{heads[u]=nexts[i];vis[i]=1;dfs(tos[i]);ans[++tt]=tos[i];las=i;}}
}
int main(){scanf("%d%d",&n,&m);for(re int i=1;i<=m;++i){int u,v;scanf("%d%d",&u,&v);g[u].push_back(v);++oudeg[u];++indeg[v];
// g[v].push_back(u); }int cnt=0,st=1;for(re int i=1;i<=n;++i){if(indeg[i]!=oudeg[i]){if(cnt>=2){puts("No");return 0;}if(oudeg[i]-indeg[i]==1)st=i;++cnt;}}for(re int i=1;i<=n;++i){sort(g[i].begin() ,g[i].end() );if(g[i].empty())continue;for(re int j=g[i].size() -1;j>=0;--j){adds(i,g[i][j]);}}dfs(st);printf("%d ",st);for(re int i=tt;i>=1;--i)printf("%d ",ans[i]);puts("");return 0;
}