定义
首先，什么是欧拉路？
生活中最熟悉的欧拉路（也是欧拉路径）应该就是小时候玩的“一笔画”游戏，要求从某个点出发，某个点停止，经过图中的每条边仅一次到达图中的一个点。
而欧拉路的定义与此相似：从图中某个图出发，遍历整个图，经过每条边有且仅有一次。
而欧拉回路就是从这个点出发，最终回到这个点。
欧拉路问题是 DFS 的一个经典应用。
判断是否存在欧拉路
要遍历完整个图，经过每一条边，就相当于除了起点和终点，其他的点你进去了就肯定要出来。
不管其他点经过多少次，你会发现：不是起点或终点的点的入度和出度都相等。
否则你进了这个点出不来，就遍历不完整个图。
而你是从起点出来，最终回到终点。那就有两种情况：
- 若起点和终点是同一个点：那么图上所有的点入度和出度都相等。因为你从这个点出去，最后回到这个点，就是出度 ，入度 ，最后入度还是等于出度。
- 若起点和终点不是同一个点：那么起点的出度比入度大1，终点的入度比出度大1。因为你从起点出来，起点入度 ，最后回到终点，终点入度 。
那么如果他有一个起点和一个终点（或是没有起点和终点），并且其他的点入度等于出度，那么他就有欧拉路。否则就没有。
并且还要判断它是否连通！如果不连通那就没有欧拉路。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
for(int i=1;i<=m;i++){
cin>>u>>v;
deg[v] ++, deg[u] --;
}
int stt=0, edd=0;
for(int i=1;i<=n;i++){
if(deg[i] == -1){
if(stt){
cout<<"No\n";
return 0;
}
stt = i;
}else if(deg[i] == 1){
if(edd){
cout<<"No\n";
return 0;
}
edd = i;
}else if(deg[i] != 0){
cout<<"No\n";
return 0;
}
}
if(stt == 0 && edd == 0){
cout<<"Yes\n";
}else if(stt == 0 || edd == 0){
cout<<"No\n";
}else cout<<"Yes\n";
|
输出一条欧拉路
根据上面的推断就可以确定这个欧拉路的起点和终点了。如果它是欧拉回路，那就随便选一个点作为起点。
从这个点开始 DFS，经过一条边就给这条边打标记，然后从这个点发散出的所有边搜索完了之后就输出这个点。
这相当于就是 DFS 回溯。而回溯的顺序正好是欧拉回路的逆序。
（图为给欧拉图 DFS 的一种顺序和其回溯的顺序）
于是就可以愉快地写代码了：
1
2
3
4
5
6
7
8
9
10
| int st[N], len;
void dfs(int x){
for(int i=h[x];i;i=edge[i].nxt){
if(!vis[i]){
vis[i] = 1;
dfs(edge[i].to);
}
}
st[++len] = x;
}
|
这道题和上面讲的不一样的是：这道题要求我们输出字典序最小的欧拉路径。
字典序最小是好办的，就让这个点能够到达的边编号最小的先 DFS，然后编号次小的再 DFS……这样就解决了字典序最小的问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| #include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
vector<int> edge[N];
int n, m;
int st[N<<1], len;
int sttvis[N];
void dfs(int x){
int siz = edge[x].size();
for(int i=sttvis[x];i<siz;i=sttvis[x]){
sttvis[x] = i+1;
dfs(edge[x][i]);
}
st[++len] = x;
}
int deg[N];
int main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin>>n>>m;
int u, v;
for(int i=1;i<=m;i++){
cin>>u>>v;
edge[u].push_back(v);
deg[v] ++, deg[u] --;
}
int stt=0, edd=0;
for(int i=1;i<=n;i++){
if(deg[i] == -1){
if(stt){
cout<<"No\n";
return 0;
}
stt = i;
}else if(deg[i] == 1){
if(edd){
cout<<"No\n";
return 0;
}
edd = i;
}else if(deg[i] != 0){
cout<<"No\n";
return 0;
}
}
if(stt == 0 && edd == 0){
stt = edd = 1;
}else if(stt == 0 || edd == 0){
cout<<"No\n";
return 0;
}
for(int i=1;i<=n;i++){
sort(edge[i].begin(), edge[i].end());
}
dfs(stt);
for(int i=len;i>=1;i--){
cout<<st[i]<<' ';
}
return 0;
}
|
