题解【模板】有向图欧拉路径
phil071128
·
·
题解
题解【模板】有向图欧拉路径
### 前置芝士:
1. **欧拉路径**
- 定义：从一个点出发，不重不漏的经过图中每一条边的一条路径（允许多次经过同一个点）。
**判断方法**
- 若为无向图，则需连通，且图中恰好存在两个点的度数是奇数，其他节点的度数为偶数，这两个度数为奇数的点就是起点与终点；或者所有点度数都是偶数。
- 若为有向图，则需连通，且图中恰好存在一个点入度比出度多一，一个点出度比入度多一，其他节点的出度等于入度；或者所有点入度等于出度。
2. **欧拉回路**
- 定义：起点和终点是一个点的欧拉路径。
- 若为无向图，则需连通，且所有点的度数都是偶数。
- 若为有向图，则需连通，且所有点的入度等于出度
在本题中，我们要在一个**有向图**中找到字典序最小的**欧拉路径**。
## Solution
既然是【模板】了,那就直接讲具体做法了。
对于欧拉路径，我们一般采用 **$\mathrm{Hierholzer}$ 算法**
- 首先我们要确定出起点，然后从起点开始不走重复边的递归。
- 对于每一个点,当访问完所有的边时，把这个点加入答案序列。
- 最后，输出答案序列即为一条欧拉路径依次经过的点。
至此,我们可以写出的基本框架了：
```cpp
void dfs(int u){
for(){ //遍历所有与u相邻的点v
if(!vis[v]){ //u与v的这条边没被访问过
vis[v]=1;
dfs(v); //递归与u相邻的点v
}
}
s.push(u); //没有边了,将u进入序列
}
```
但这样**时间复杂度**是不对的。按照算法，我们不能走重复边，但如果每次都vis判断一遍，则会出现很多次访问同一条边，时间复杂度是不正确的。
#### 处理：
对于任意一个点 $u$ 来说，建完图之后访问边是有顺序的，我们新开一个数组 $delete $ 记录访问到哪个位置即可（即该删除哪个位置）。
这题另一个 ex 的地方还是在于**按照字典序输出** 。
## Code
#### 判断是否有欧拉路径部分：
```cpp
//有向图欧拉路径：一个点入度=出度+1，一个点出度=入度+1，其余点(或所有点)入度=出度
bool flag1=1;//所有点入度是否出度
int sum1=0,sum2=0;//出度-入度=1的数量 和 入度-出度=1的数量
for(int i=1;i<=n;i++){
if(chu[i]!=ru[i]){
flag1=0;
}
if(chu[i]-ru[i]>1){
cout<<"No";
return 0;
}
if(chu[i]-ru[i]==1){
start=i;
sum1++;
}
if(ru[i]-chu[i]==1){
sum2++;
}
}
if(!(flag1==1||(sum1==sum2)&&sum1==1)){
cout<<"No";
return 0;
}
```
#### 邻接矩阵 60pts:
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int ru[N],chu[N],mapp[N][N],n,m;
int delet[N]; //记录该访问(删除)哪个点
stack <int> s;
void dfs(int u){
for(int v=1;v<=n;v++){ //遍历所有点
if(mapp[u][v]>0){ //有边,说明u与v相连
mapp[u][v]--; //删边
dfs(v); //递归
}
}
s.push(u);
}
int main(){
cin>>n>>m;
int u,v;
for(int i=1;i<=m;i++){
cin>>u>>v;
mapp[u][v]++; // 邻接矩阵
chu[u]++,ru[v]++; //统计点的出度和入度
}
int start=1;
//判断部分
dfs(start);
while(!s.empty()){
cout<<s.top()<<" ";
s.pop();
}
return 0;
}
```
为什么这里要提到邻接矩阵呢，因为邻接矩阵有个极大的优点就是**不需要排序**（类似于桶），不用考虑字典序的问题。
### vector 模拟邻接表 100pts
注：vector的排序方法
```cpp
sort(a.begin(),a.end(),cmp);
```
------------
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int ru[N],chu[N],n,m;
stack <int> s;
int delet[N];
vector <int> a[N];
void dfs(int u){
for(int i=delet[u];i<a[u].size();i=delet[u]){
delet[u]=i+1;
dfs(a[u][i]);
}
s.push(u);
}
int main(){
cin>>n>>m;
int u,v;
for(int i=1;i<=m;i++){
cin>>u>>v;
a[u].push_back(v);
chu[u]++,ru[v]++;
}
for(int i=1;i<=n;i++){
sort(a[i].begin(),a[i].end());
}
int start=1;
bool flag1=1;
int sum1=0,sum2=0;
for(int i=1;i<=n;i++){
if(chu[i]!=ru[i]){
flag1=0;
}
if(chu[i]-ru[i]>1){
cout<<"No";
return 0;
}
if(chu[i]-ru[i]==1){
start=i;
sum1++;
}
if(ru[i]-chu[i]==1){
sum2++;
}
}
if(!(flag1==1||(sum1==sum2)&&sum1==1)){
cout<<"No";
return 0;
}
dfs(start);
while(!s.empty()){
cout<<s.top()<<" ";
s.pop();
}
return 0;
}