在一張圖中，從一個點出發每條邊經過且只經過一次得到的路徑，如果最后回到起點，那么就是歐拉回路，如果最后沒有回到起點，那么得到的就是歐拉路徑。

在無向圖中，歐拉路徑滿足的要求是，除了起點和終點以外其他點的度數都是偶數；歐拉回路滿足的要求是所有點的度數都是偶數。

在有向圖中，歐拉路徑滿足的要求是：除了起點和終點外，其他點的出度等于入度，起點的出度比入度多1，終點的入度比出度多1；在歐拉回路中，所有點的出度等于入度。

通常找歐拉路徑的算法就是dfs遍歷，但是這里的判重是判重邊，而非判重點。而且是當一個點所有的邊都遍歷結束后才會將該點算入答案。我們以一個點為例，若有m條自環路徑，那么每條路徑出就要開一層，一直往下遞歸。那么時間復雜度就變成m^2,這個時間復雜度很高，所有我們由此產生優化，遍歷一條邊那么就把它刪掉，以防后面再次遍歷到這條邊，產生不必要的冗余。但是這里如果僅僅通過h[u]=ne[i]來刪除，后面遍歷時可以生效，但是回溯到前面遍歷并不是再從開頭開始，所以并沒有生效(或者換個角度來理解，我們的刪除相當于直接將頭節點的指針往后移，但是中間節點的指針是沒有改變的，所以實際上前面的循環應該已經到了中間那么節點的部分，它們之間的指向關系并沒有改變，仍然會產生新的遞歸循環)時間復雜度還是很高，那么該如何處理呢，我們這里通過傳入指針來實現動態的刪除。

void dfs(int u)
{for (int &i = h[u]; ~i;){if (used[i]){i = ne[i];continue;}used[i] = true;if (type == 1) used[i ^ 1] = true;int t;if (type == 1){t = i / 2 + 1;if (i & 1) t = -t;}else t = i + 1;int j = e[i];i = ne[i];dfs(j);ans[ ++ cnt] = t;}
}

我們在定義的時候定義int &i=h[u]，修改i的時候，h[u]也被同步修改了，往后遞歸的時候，我們每次都從h[u]開始，h[u]不是一成不變的，修改i相當于修改h[u]，修改h[u]相當于修改中間節點的指向，中間節點的指向關系變了，那么往前回溯的過程中就不會出現剛剛m^2的問題了。

1123. 鏟雪車（活動 - AcWing）

這里有個很迷惑人的條件，鏟雪的時候前進速度是20，不鏟雪的時候前進速度是50，但是顯然不鏟雪的前提是學已經鏟過了，那么就相當于這條路走了兩邊，當然是只走一遍更劃算。每條道路的兩個方向均需要鏟雪，所以每條路徑的出度等于入度，那么就是歐拉回路，所以我們可以保證每條路徑只經過一次，所以我們統計出所有的路徑再除20即可。這里的時間轉化，我們可以先求出分鐘數，然后再進行轉化。

#include<bits/stdc++.h>
using namespace std;
int s,t;
double getd(double a,double b,double c,double d)
{double dx=a-c,dy=b-d;double res=dx*dx+dy*dy;return sqrt(res);
}
int main()
{scanf("%d%d",&s,&t);double a,b,c,d;double ans=0;while(~scanf("%lf%lf%lf%lf",&a,&b,&c,&d)){double sd=getd(a,b,c,d);ans += 2*sd;}int m=round(ans/1000/20*60);int h=m/60;m%=60;printf("%d:%02d",h,m);}

1184. 歐拉回路(活動 - AcWing)

要注意，歐拉回路和歐拉路徑中是可以有孤立點的，經過所有邊，不一定經過所有點，所以dfs要找一個有出邊的點開始遍歷/

#include<bits/stdc++.h>
using namespace std;
const int N=100010,M=400010;
int t,n,m;
int cnt;
int ans[M],used[M];
int h[N],e[M],ne[M],idx;
int din[N],dout[N];
void add(int a,int b)
{e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u)
{for(int &i = h[u];~i;){if(used[i]){i=ne[i];continue;}used[i]=1;if(t==1) used[i^1]=1;int res;if(t==1){res=i/2+1;if(i&1) res*=-1;}else res=i+1;int j=e[i];i=ne[i];dfs(j);ans[++cnt]=res;}}
int main()
{scanf("%d%d%d",&t,&n,&m);memset(h,-1,sizeof h);for(int i=1;i<=m;i++){int a,b;scanf("%d%d",&a,&b);add(a,b);if(t==1) add(b,a);din[b]++,dout[a]++;}if(t==1){for(int i=1;i<=n;i++){if(din[i]+dout[i]&1){printf("NO");return 0;}}}else{for(int i=1;i<=n;i++){if(din[i]!=dout[i]){printf("NO");return 0;}}}for(int i=1;i<=n;i++){if(h[i]!=-1){dfs(i);break;}}if(cnt!=m) printf("NO\n");else{printf("YES\n");for(int i=cnt;i>=1;i--){printf("%d ",ans[i]);}}
}

?另外要注意我們dfs求得的路徑是從終點到起點的，所以輸出的時候需要倒著輸出。

1124. 騎馬修柵欄（1124. 騎馬修柵欄 - AcWing題庫）

這里我們需要輸出經過的節點，同時使得在有多組解的情況下輸出節點序最小的那組解。那么我們首先應該找到最小的有出邊的點，從這里開始遍歷，另外為了使得后面的點也是小的在前面，我們需要先遍歷所有出邊中連接的點編號最小的出邊，那么可以用鄰接矩陣來存邊。

本題不確定是求歐拉回路還是歐拉路徑，所以我們先找出第一個有邊的點，然后遍歷查找是否有度為奇數點，如果有就替換，否則就直接搜歐拉回路。

#include<bits/stdc++.h>
using namespace std;
const int N=510;
int n;
int g[N][N],ans[N*N],cnt,d[N];
void dfs(int u)
{for(int i=1;i<=500;i++){if(g[u][i]){g[u][i]--,g[i][u]--;dfs(i);}}ans[++cnt]=u;
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){int a,b;scanf("%d%d",&a,&b);g[a][b]++,g[b][a]++;d[a]++,d[b]++;}int s=1;while(!d[s])s++;for(int i=s;i<=500;i++){if(d[i]%2) {s=i;break;}}dfs(s);for(int i=cnt;i>=1;i--) printf("%d\n",ans[i]);}

1185. 單詞游戲（活動 - AcWing）

思路：這里如果將單詞視為節點顯然建邊太麻煩了，我們可以用之前的一個思路，在一個單詞的首尾字母之間建邊，這樣的話就只有26個點，實現復雜度一下就降低了。

?那么就要想是建有向邊還是無向邊，我們要注意順序問題，所以建的是有向邊。然后實際上不用真的去搜，只需要判斷一下每個點的出度入度是否符合要求，然后判斷一下邊是否連通。這里判斷邊是否連通不用dfs，我們用并查集來判斷。

#include<bits/stdc++.h>
using namespace std;
const int N=30,M=200010;
int st[M];
int dout[N],din[N];
int p[N];
int find(int x)
{if(x!=p[x]) p[x]=find(p[x]);return p[x];
}
int main()
{int t;scanf("%d",&t);while(t--){int n;scanf("%d",&n);memset(st,0,sizeof st);memset(din,0,sizeof din);memset(dout,0,sizeof dout);for(int i=0;i<26;i++) p[i]=i;for(int i=1;i<=n;i++){string s;cin>>s;int a=s[0]-'a',b=s[s.size()-1]-'a';st[a]=st[b]=1;dout[a]++,din[b]++;p[find(a)]=find(b);}int flag=1,sc=0,ec=0;for(int i=0;i<26;i++){if(dout[i]-din[i]==1) sc++;else if(din[i]-dout[i]==1) ec++;else if(din[i]!=dout[i]) {flag=0;break;}}if (flag && !(!sc && !ec || sc== 1 && ec == 1)) flag = 0;int rep=-1;for(int i=0;i<26;i++){if(st[i]){if(rep==-1) rep=find(i);else if(rep!=find(i)){flag=0;break;}}}if(!flag) printf("The door cannot be opened.\n");else printf("Ordering is possible.\n");}
}

這題判斷邊是否連通也可以用dfs來寫，只不過時間復雜度太高了，會超時，這里還是把代碼放上。

#include<bits/stdc++.h>
using namespace std;
const int N=30,M=200010;
int st[M];
int dout[N],din[N];
int p[N];
int h[N],e[M],ne[M],idx;
int used[M];
int cnt;
void add(int a,int b)
{e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u)
{for (int &i = h[u]; ~i;){if (used[i]){i = ne[i];continue;}used[i] = true;int j = e[i];i = ne[i];dfs(j);cnt++;}
}
int main()
{int t;scanf("%d",&t);while(t--){int n;scanf("%d",&n);memset(used,0,sizeof used);memset(din,0,sizeof din);memset(dout,0,sizeof dout);memset(h,-1,sizeof h);for(int i=1;i<=n;i++){string s;cin>>s;int a=s[0]-'a',b=s[s.size()-1]-'a';dout[a]++,din[b]++;add(a,b);}int flag=1,sc=0,ec=0;for(int i=0;i<26;i++){if(dout[i]-din[i]==1) sc++;else if(din[i]-dout[i]==1) ec++;else if(din[i]!=dout[i]) {flag=0;break;}}if (flag && !(!sc && !ec || sc== 1 && ec == 1)) flag = 0;if(!flag) printf("The door cannot be opened.\n");//判連通else {int s=0;while(!dout[s]) s++;for(int i=0;i<26;i++)if(dout[i]-din[i]==1){s=i;break;}dfs(s);if(cnt<n) printf("The door cannot be opened.\n");else printf("Ordering is possible.\n");}}
}

所以可以見得，判斷歐拉回路和歐拉路徑，只要判斷度和連通性的性質滿足即可，方法不唯一。