【算法】浅谈欧拉路径
lnwhl
·
·
个人记录
## $\text{Part 1}$ 一些概念
**欧拉路径**是什么呢？
其实就是一笔画问题。
抽象成数学语言：
**通过图中所有边恰好一次且行遍所有顶点的通路称为欧拉路径**。
如果起点和终点相同，该路径又称为**欧拉回路**。
## $\text{Part 2}$ 欧拉路径的判断
### $\text{Part 2.1}$ 无向图
- 其实就是标准的一笔画问题。
- 我们要计算每个点的**度**。
- 如果**度为奇数的点**的个数是 $0$ 或 $2$，那么就有欧拉路径。
### $\text{Part 2.2}$ 有向图
- 如果是有向图，我们要计算每个点的**入度**和**出度**。
- 如果是欧拉路径，需要是如下两种情况之一。
- **起点的入度比出度小 $1$，终点的入度比出度大 $1$，其余的点入度等于出度**（普通欧拉路径）。
- **所有的点入度等于出度**（欧拉回路）。
## $\text{Part 3}$ 代码实现
[P7771 【模板】欧拉路径](https://www.luogu.com.cn/problem/P7771)
有向图的欧拉路径。用栈维护路径。求字典序，所以排个序。
$nxt$ 数组保证都遍历到且不重复。
```cpp
#include <bits/stdc++.h>
#define Rint register int
using namespace std;
const int N=1e5+5;
int n,m,d[N][2],nxt[N];
stack<int>st;
vector<int>t[N];
inline void dfs(int s)
{
for(Rint i=nxt[s];i<t[s].size();i=nxt[s])//i=nxt[s] 不能是 i++ 因为可能重复遍历
{
nxt[s]=i+1;
dfs(t[s][i]);
}
st.push(s);
}
int main()
{
scanf("%d%d",&n,&m);
for(Rint i=1;i<=m;++i)
{
int u,v;scanf("%d%d",&u,&v);
t[u].push_back(v);
d[u][1]++;d[v][0]++;//d[][1]表示出度，d[][0]表示入度
}
for(Rint i=1;i<=n;++i)
sort(t[i].begin(),t[i].end());//排序以保证字典序最小
int fl=1,cnt1=0,cnt2=0,St=1;//St需要初始化，防止是欧拉回路
for(Rint i=1;i<=n;++i)
{
if(d[i][0]!=d[i][1])fl=0;//判断是不是欧拉回路
if(d[i][1]-d[i][0]==1)cnt1++,St=i;//起点
if(d[i][0]-d[i][1]==1)cnt2++;//终点
}
if((!fl)&&!(cnt1==1&&cnt2==1))//判断是否有解
{
cout<<"No";return 0;
}
dfs(St);
while(!st.empty())
{
cout<<st.top()<<" ";
st.pop();
}
return 0;
}
```