借鉴文章
\(1\). 欧拉路径定义：
图中经过所有边恰好一次的路径叫欧拉路径（也就是一笔画）。如果此路径的起点和终点相同，则称其为一条欧拉回路。
\(2.\) 欧拉路径判定（是否存在）：
-
有向图欧拉路径：图中恰好存在 \(1\) 个点出度比入度多 \(1\)（这个点即为 起点 \(S\)），\(1\) 个点入度比出度多 \(1\)（这个点即为 终点 \(T\)），其余节点出度=入度。
-
有向图欧拉回路：所有点的入度=出度（起点 \(S\) 和终点 \(T\) 可以为任意点）。
-
无向图欧拉路径：图中恰好存在 \(2\) 个点的度数是奇数，其余节点的度数为偶数，这两个度数为奇数的点即为欧拉路径的 起点 \(S\) 和 终点 \(T\)。
-
无向图欧拉回路：所有点的度数都是偶数（起点 \(S\) 和终点 \(T\) 可以为任意点）。
注：存在欧拉回路（即满足存在欧拉回路的条件），也一定存在欧拉路径。
当然，一副图有欧拉路径，还必须满足将它的有向边视为无向边后它是连通的（不考虑度为 \(0\) 的孤立点），连通性的判断我们可以使用并查集或 dfs 等。
例题
欧拉路径
点击查看代码
#include <bits/stdc++.h>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define pb push_back
#define ull unsigned long long
#define pii pair<int,int>
#define lid (rt<<1)
#define rid (rt<<1|1)
using namespace std;
const int N = 1e5+5;
std::vector<int> edge[N];
int n,m;
int in[N],out[N],cnt[2],del[N];
stack <int> sta;bool vis[N];
int main()
{
speed();
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
cin>>n>>m;
int u,v;
for(int i=1;i<=m;i++)
{
cin>>u>>v;
edge[u].push_back(v);
out[u]++;in[v]++;
}
for(int i=1;i<=n;i++) sort(edge[i].begin(),edge[i].end());
bool equal=1;int st=1;//注意默认起点
for(int i=1;i<=n;i++)
{
if(out[i]!=in[i])
{
equal=0;
if(out[i]-in[i]==1)cnt[1]++,st=i;
else if(in[i]-out[i]==1)cnt[0]++;
else return cout<<"No"<<endl,0;
}
}
if((!equal)&&!(cnt[0]==cnt[1]&&cnt[0]==1)) return cout<<"No"<<endl,0;
auto dfs=[&](auto dfs,int u) ->void{
for(int i=del[u];i<edge[u].size();i=del[u])
{
del[u]=i+1;int to=edge[u][i];
dfs(dfs,to);
}
sta.push(u);
};
dfs(dfs,st);
while(sta.size())cout<<sta.top()<<" ",sta.pop();
return 0;
}
骑马修栅栏
点击查看代码
#include <bits/stdc++.h>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define pb push_back
#define ull unsigned long long
#define pii pair<int,int>
#define lid (rt<<1)
#define rid (rt<<1|1)
using namespace std;
const int N = 1e4+5;
std::vector<int> edge[N];
int n,m;
int du[N],mp[N][N],st;
stack <int> sta;bool vis[N];
int mi=1e9;
int main()
{
speed();
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
cin>>m;
int u,v;
for(int i=1;i<=m;i++)
{
cin>>u>>v;
mp[u][v]++;mp[v][u]++;
du[u]++;du[v]++;
n=max(n,u);n=max(n,v);
mi=min(u,mi);mi=min(mi,v);
}
st=mi;//注意默认起点
for(int i=1;i<=n;i++)
{
du[i]%2?({st=i;break;}):({continue;});
}
auto dfs=[&](auto dfs,int u) ->void{
for(int i=1;i<=n;i++)
{
if(mp[u][i])
{
mp[u][i]--;
mp[i][u]--;
dfs(dfs,i);
}
}
sta.push(u);
};
dfs(dfs,st);
while(sta.size())cout<<sta.top()<<endl,sta.pop();
return 0;
}