欧拉路径的定义
如果图G中的一个路径包括每个边恰好一次，则该路径称为欧拉路径(Euler path)。
如果一个回路是欧拉路径，则称为欧拉回路(Euler circuit)。
具有欧拉回路的图称为欧拉图（简称E图）。具有欧拉路径但不具有欧拉回路的图称为半欧拉图。
其实就是 一笔从起点经过所有边到达终点（欧拉路） 和 一笔从起点经过所有边回到起点（欧拉回路）
无向图
欧拉回路：只要每个点的度数均为偶数即可。
因为每个点的度数为偶数，所以可以将整个图看做由数个环嵌套而成，因为环一定能找到一条欧拉回路，所以整个图也能找到欧拉回路。
欧拉路径：如果有且仅有两个点的度数为奇数，就会存在一条从这两个中的一个到达另一个的欧拉路径。
假如在这两个点间连一条边，就能够从任意一个点出发找到一条欧拉回路，当出发点为这两个点中的一个时，切断这条边，就成为一条欧拉路径了。
有向图
欧拉回路：所有点的入度等于出度，就存在一条欧拉回路。
这里可以换一种角度来理解，对于每一个点，每次进入这个节点，就一定有一条路可以出去，因此必定存在一条欧拉回路。
欧拉路径：最多有一点入度等于出度+1，最多有一点入度等于出度-1，就会有一条从出度大于入度（没有则等于）的点出发，到达出度小于入度（没有则等于）的点的一条欧拉路径。证明方法与无向图的欧拉路径类似。
Hierholzer算法
算法流程（无向图）：
1.判断奇点数。奇点数若为0则任意指定起点，奇点数若为2则指定起点为奇点。
2.开始递归函数Hierholzer(x):
循环寻找与x相连的边(x,u):
删除(x,u)
删除(u,x)
Hierholzer(u);
将x插入答案队列之中
3.倒序输出答案队列
对于该图，算法的执行流程如下：
1.找到该图没有奇点，从1开始进行Hierholzer算法。
2.删边1-2 递归到2
3.删边2-3 递归到3
4.删边3-7 递归到7
5.删边7-1 递归到1
6.1无边，1加入队列，返回
7.7加入队列，返回
8.删边3-4 递归到4
9.删边4-5 递归到5
10.删边5-6 递归到6
11.删边6-3 递归到3
12.3加入队列，返回
13.6加入队列，返回
14.5加入队列，返回
15.4加入队列，返回
16.3加入队列，返回
17.2加入队列，返回
18.1加入队列，返回
答案队列为：1 7 3 6 5 4 3 2 1。反向输出即为答案。
有向图除判断是否存在有一点点不同以外同理。
对于该题【欧拉路径/欧拉回路】模板题，要求输出答案的最小序列。所以起点首先要选的尽量小，然后在边的储存上面加一点小trick。
使用邻接表储存图时，除了用链式前向星还可以用vector储存。我们可以把vector换成multiset，这样就可以保证该点前往的下一个点是最小值，同时保证了答案的最小值。
LuoguP1341无序字母对
1 //欧拉路径：两个点为奇数度； 2 //欧拉回路，全为偶数度 3 #include<bits/stdc++.h> 4 #define MAXN 150 5 using namespace std; 6 int n,f[MAXN][MAXN]/*邻接矩阵存图*/,deg[MAXN],fa[MAXN]/*并查集求联通*/; 7 char ans[2000];//存答案 8 int find(int x) 9 { 10 if(fa[x]!=x) 11 fa[x]=find(fa[x]); 12 return fa[x]; 13 } 14 void dfs(int cur) 15 { 16 for(int i=64;i<=125;i++) 17 { 18 if(f[cur][i]) 19 { 20 f[cur][i]=f[i][cur]=0; 21 dfs(i); 22 } 23 } 24 ans[n--]=cur;//倒序存 25 } 26 int main() 27 { 28 cin>>n; 29 for(int i=64;i<=125;i++)fa[i]=i;//A~z 30 for(int i=1;i<=n;i++) 31 { 32 string str;cin>>str; 33 f[str[0]][str[1]]=f[str[1]][str[0]]=1; 34 deg[str[0]]++;deg[str[1]]++; 35 fa[find(str[0])]=find(str[1]);//建立连通图 36 } 37 int cnt=0,head=0; 38 for(int i=64;i<=125;i++) 39 { 40 if(fa[i]==i&°[i])cnt++;//判断祖宗节点 41 } 42 if(cnt!=1){cout<<"No Solution"<<endl;return 0;}//不连通图 43 cnt=0; 44 for(int i=64;i<=125;i++) 45 { 46 if(deg[i]&1){ 47 cnt++; 48 if(head==0)head=i; 49 } 50 } 51 if(cnt&&cnt!=2){cout<<"No Solution"<<endl;return 0;}//没有欧拉路径 52 if(head==0) 53 { 54 for(int i=64;i<=125;i++) 55 if(deg[i]){head=i;break;} 56 } 57 dfs(head); 58 cout<<ans<<endl; 59 return 0; 60 }
Luogu2731骑马修栅栏
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define MAXN 2000 4 using namespace std; 5 multiset<int>to[MAXN]; 6 vector<int>q; 7 int n; 8 void dfs(int cur) 9 { 10 for(auto i=to[cur].begin();i!=to[cur].end();i=to[cur].begin()) 11 { 12 to[cur].erase(i); 13 to[*i].erase(to[*i].find(cur)); 14 dfs(*i); 15 } 16 q.push_back(cur); 17 } 18 int main() 19 { 20 cin>>n; 21 //此题数据保证有解，否则需要并查集判断是否联通 22 //题意是欧拉路径/回路 23 for(int i=1;i<=n;i++) 24 { 25 int a,b;cin>>a>>b; 26 to[a].insert(b); 27 to[b].insert(a); 28 } 29 int head=0; 30 for(int i=1;i<=1024;i++) 31 { 32 if(!to[i].empty()&&head==0)head=i;//选择最小的点 33 if(to[i].size()&1){//找到奇度 34 head=i; 35 break; 36 } 37 } 38 dfs(head); 39 for(int i=q.size()-1;i>=0;i--)cout<<q[i]<<endl; 40 return 0; 41 }