定義

歐拉路問題，俗稱“一筆畫”問題，即給定一張圖，若存在一條從點 \(S\) 到點 \(T\) 的路徑恰好不重不漏地經(jīng)過每條邊一次，則稱該路徑為 \(S\) 到 \(T\) 的歐拉路；特別地，若 \(S\) 和 \(T\) 為同一點，則稱該路徑為歐拉回路

判定

一張無向圖有歐拉路，當且僅當所有點度數(shù)均為偶數(shù)（此時圖為歐拉圖）或有且僅有兩個點度數(shù)為奇數(shù)（此時圖為半歐拉圖）；有歐拉回路，當且僅當所有點度數(shù)均為偶數(shù)

一張有向圖有歐拉路，當且僅當所有點出度等于入度（此時圖為歐拉圖）或有且僅有一個點入度恰比出度大 \(1\)，一個點入度恰比出度小 \(1\)（此時圖為半歐拉圖）；有歐拉回路，當且僅當所有點入度等于出度

求法

使用 \(DFS\) 遍歷即可求出一條歐拉路的可行路徑

如果有且僅有兩個點度數(shù)為奇數(shù)，從其中一個點開始遍歷；否則因為有回路，任意一點開始遍歷即可

考慮經(jīng)過一個點時，將這個點所在的回路全部加入路徑中，最后再加入這個點

直接樸素實現(xiàn)需要一遍 \(DFS\) 找回路并存儲，一遍 \(DFS\) 將回路加入最終歐拉路徑中，較為麻煩

考慮一個點的回溯代表的含義：要找的歐拉路在這個點之后的點已經(jīng)走完了

那么這個時候存下這個點，最終即可得到一條 反著的 歐拉路

于是我們在 \(DFS\) 即將回溯的時候直接把點放進一個棧中，最后彈棧就是要找的歐拉路

可能會有一個疑問：為什么不能在 \(DFS\) 的過程中經(jīng)過一個點就直接把一個點放入路徑中，只能在回溯的時候記錄？

考慮半歐拉圖上搜到某點與那個入度比出度大1/小1的點相連，此時若直接存且不幸先搜到這個奇數(shù)點將會直接把這個點放進路徑中，相當于提前走上了一條不歸路，顯然不對；

而在棧的存法下這個奇數(shù)點是最先入棧的,即最后輸出的,沒有問題

模板題代碼：

#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;

inline int read()
{
	int x=0,fu=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')fu=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*fu;
}
void write(int x)
{
	if(x<0)	x=-x,putchar('-');
	if(x<10){putchar(x+'0');return;}
	write(x/10);putchar(x%10+'0');
}

const int N=1e5+10;
vector<pii>ed[N];
int n,m;
int in[N],out[N];
stack<int>st;
int now[N];
void dfs(int u)
{
	for(int v=now[u];v<ed[u].size();v=now[u])
	{
		if(ed[u][v].se)	continue;
		ed[u][v].se=1;
		now[u]=v+1;
		dfs(ed[u][v].fi);
	}
	st.push(u);
}

signed main()
{
	n=read(),m=read();
	for(int i=1;i<=m;i++)
	{
		int u=read(),v=read();
		ed[u].push_back({v,0});
		out[u]++,in[v]++;
	}
	int sg1=0,sg2=0;
	for(int i=1;i<=n;i++)
	{
		if(in[i]==out[i])	continue;
		if(in[i]-out[i]==1)
		{
			if(sg1)
			{
				puts("No");
				return 0;
			}
			sg1=i;
		}
		else if(in[i]-out[i]==-1)
		{
			if(sg2)
			{
				puts("No");
				return 0;
			}
			sg2=i;
		}
		else
		{
			puts("No");
			return 0;
		}
	}
	if((!sg1&&sg2)||(sg1&&!sg2))
	{
		puts("No");
		return 0;
	}
	for(int i=1;i<=n;i++)	sort(ed[i].begin(),ed[i].end());
	if(sg1)	dfs(min(sg1,sg2));
	else	dfs(1);
	while(!st.empty())	write(st.top()),putchar(' '),st.pop();
	return 0;
 } 

后記：網(wǎng)絡(luò)流和歐拉路當前弧優(yōu)化的區(qū)別

在復(fù)健圖論時無意中發(fā)現(xiàn)歐拉路的當前弧優(yōu)化與 \(dinic\) 不同，然后發(fā)現(xiàn)自己其實并沒有完全學(xué)懂這兩個算法
網(wǎng)絡(luò)流：

for(int i=now[u];~i&&res;i=nxt[i])
{
	...
	now[u]=i;
	...
}

這里的 \(now\) 不能直接變下一條邊而只能停在“當前”，因為當前這條邊的流量不一定流完，即網(wǎng)絡(luò)流有可能再用這條邊

如果掃到這條邊后直接跳了當前弧就會導(dǎo)致增廣路的利用其實是不到位的，甚至可能導(dǎo)致一直有增廣路但是一直走不到的極端情況

歐拉路：

for(int v=now[u];v<ed[u].size();v=now[u])
{
	...
	now[u]=v+1;
	...
}

這里的 \(now\) 就必須直接變下一條邊，因為一條邊只需要走一次，下一條邊才是“當前”，即 歐拉路不可能再用這條邊

如果不跳下一條邊這條無用的邊就會被再次找，當前弧優(yōu)化的意義就有限了