【学习笔记】欧拉回路
NCC79601
2019-03-25 13:05:19
欧拉回路是指：在一个连通图$G$中，若存在一条**回路**使得$G$中的**每条边都被且仅被经过一次**，这条回路就叫**欧拉回路**，这个图就是**欧拉图。**
另外，在一个连通图$G$中，若存在一条**路径**使得$G$中的**每条边都被且仅被经过一次**，这条路径就叫**欧拉通路**，这个图就是**半欧拉图**。
很显然，如果统计所有点的度数$deg[i]$，对于一个欧拉图，**不存在**一个点$u$的入度$deg[u]$为奇数；对于一个半欧拉图，**有且仅有两个**点$u,v$的度数$deg[u],deg[v]$为奇数，且该图中的欧拉通路以$u,v$为端点。
# $\textbf{Hierholzer}$算法
$Hierholzer$算法是指：在一个欧拉图$G$中，随机选取一个点作为起始点，每次遍历点$u$所连接的点$v$，对于点$v$，先删去无向边$<u,v>$，然后对点$v$跑$\text{dfs}$。循环结束后，将$u$**倒序**记录在$res[i]$数组中。算法结束后，$res[i]$中的路径就是一条欧拉回路。
下面是用邻接矩阵存图后的$Hierholzer$算法实现。
```cpp
inline void dfs(int i) {
for(register int j = 1; j <= MAXN; j++) {
if(G[i][j]) {
G[i][j] = G[j][i] = 0;
dfs(j);
}
}
res[tail--] = i;
}
```
## 例题 [P1341](https://www.luogu.org/problemnew/show/P1341)
**思路：** 给出的字母对实际上就是在构造边，存完边之后直接跑$Hizerholzer$即可。由于要保证字典序最小，所以只需要注意在遍历的时候按照字典序从小到大遍历就可以了。
```cpp
//code
#include<bits/stdc++.h>
using namespace std;
const int MAXN = (int)'z' + 10;
int G[MAXN][MAXN];
int deg[MAXN];
char res[MAXN * MAXN];
int n, tail;
inline void dfs(int i) {
for(register int j = 'A'; j <= 'z'; j++) {
if(G[i][j]) {
G[i][j] = G[j][i] = 0;
dfs(j);
}
}
res[tail--] = (char)i;
}
int main() {
scanf("%d", &n);
tail = n;
for(register int i = 1; i <= n; i++) {
char s[10];
scanf("%s", s);
G[s[0]][s[1]] = G[s[1]][s[0]] = 1;
deg[s[0]]++, deg[s[1]]++;
}
char begin = 0;
int cnt = 0;
for(register int i = 'A'; i <= 'z'; i++) {
if(deg[i] % 2) {
cnt++;
if(!begin)
begin = (char)i;
}
}
if(cnt && cnt != 2) {
printf("No Solution");
return 0;
}
if(!begin)
for(register int i = 'A'; i <= 'z'; i++)
if(deg[i]) {
begin = (char)i;
break;
}
dfs(begin);
puts(res);
return 0;
}
```