一. 基本概念
-
欧拉图是指通过图（无向图或有向图）中所有边且每边仅通过一次通路，相应的回路称为欧拉回路。具有欧拉回路的图称为欧拉图（
E
u
l
e
r
G
r
a
p
h
Euler Graph
EulerGraph），具有欧拉通路而无欧拉回路的图称为半欧拉图。（f
r
o
m
from
from百度百科） -
有没有发现很像小时候玩的一笔画问题？
欧拉路分为欧拉通路和欧拉回路
欧拉通路：从一个点出发，不重复地经过每条边，从另一个点结束。
欧拉回路：从一个点出发，不重复地经过每条边，又回到该点结束。
判断方法（性质）：
通路：有且仅有两个点的度数为奇数，其他点的度数均为偶数。
回路：所有点的度数均为偶数。
通路：有一个点的出度比入度大
1
1
1,另一个点的出度比入度小
1
1
1，其他点的出度与入度相等。
回路：所有点的出度与入度相等。
二. 判断方法
判断一个图是否有欧拉通路或欧拉回路，一般用到弗勒里（
F
l
e
u
r
y
Fleury
Fleury）算法。
该算法用
D
F
S
DFS
DFS 实现。（大法师又双叒叕登场了）
Fleury 算法的核心是：除非都是桥，否则走非桥边。
{\color{Red}\colorbox{White}{Fleury 算法的核心是：除非都是桥，否则走非桥边。}}
Fleury 算法的核心是：除非都是桥，否则走非桥边。
但实际上并不需要判断是不是桥，当走完某条边后不能再走时，
{\color{Green}\colorbox{White}{但实际上并不需要判断是不是桥，当走完某条边后不能再走时，}}
但实际上并不需要判断是不是桥，当走完某条边后不能再走时，
我们将其放入栈内（不是队列！！！），当全部边都走过后再把栈内的边
{\color{Green}\colorbox{White}{我们将其放入栈内（不是队列！！！），当全部边都走过后再把栈内的边}}
我们将其放入栈内（不是队列！！！），当全部边都走过后再把栈内的边
输出。
{\color{Green}\colorbox{White}{输出。}}
输出。
举个栗子
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2LY2mxJ3-1628826096050)(https://cdn.luogu.com.cn/upload/image_hosting/kr87171y.png)]
D
F
S
DFS
DFS 开始，从
1
1
1 号点出发，我们的遍历顺序：
1
→
2
2
→
3
3
→
1
1 \to 2 \quad 2 \to 3 \quad 3 \to 1
1→22→33→1
这时发现走不动了，于是我们回溯到
3
3
3 号点，栈内情况：
|
3 → 1 3 \to 1 3→1 |
|---|
3
3
3 号点也走不了了，回溯到
2
2
2 号点，栈内情况:
|
2 → 3 2 \to 3 2→3 |
|---|
|
3 → 1 3 \to 1 3→1 |
2
2
2 号点继续走：
2
→
4
4
→
5
5
→
2
2 \to 4 \quad 4 \to 5 \quad 5 \to 2
2→44→55→2
2
2
2 号点走不了了，回溯，栈内情况：
|
5 → 2 5 \to 2 5→2 |
|---|
|
2 → 3 2 \to 3 2→3 |
|
3 → 1 3 \to 1 3→1 |
5
5
5 号点回溯：
|
4 → 5 4 \to 5 4→5 |
|---|
|
5 → 2 5 \to 2 5→2 |
|
2 → 3 2 \to 3 2→3 |
|
3 → 1 3 \to 1 3→1 |
4
4
4 号点回溯：
|
2 → 4 2 \to 4 2→4 |
|---|
|
4 → 5 4 \to 5 4→5 |
|
5 → 2 5 \to 2 5→2 |
|
2 → 3 2 \to 3 2→3 |
|
3 → 1 3 \to 1 3→1 |
2
2
2 号点回溯：
|
1 → 2 1 \to 2 1→2 |
|---|
|
2 → 4 2 \to 4 2→4 |
|
4 → 5 4 \to 5 4→5 |
|
5 → 2 5 \to 2 5→2 |
|
2 → 3 2 \to 3 2→3 |
|
3 → 1 3 \to 1 3→1 |
1
1
1 号点也走不了，
D
F
S
DFS
DFS 结束。
最终输出路径：
1
→
2
2
→
4
4
→
5
5
→
2
2
→
3
3
→
1
1 \to 2 \quad 2 \to 4 \quad 4 \to 5 \quad 5 \to 2 \quad 2 \to 3 \quad 3 \to 1
1→22→44→55→22→33→1
这是一条符合条件的路径。
三. 小试牛刀
Problem A: 世界人民大团结
S
p
e
c
i
a
l
J
u
d
g
e
\color{Red}{Special\,Judge}
SpecialJudge
Description
现在，世界的主题是和平与发展。社会学博士老
Z
Z
Z 认为，要实现和平发展，首先要实现世界人民大团结。
世界上有
n
n
n 个人。他们胸前和背后各有一个自然数，大于或等于
0
0
0 且小于或等于
6
6
6。两个身上带有某个相同数字的人把身上相同的数字合在一起，就实现了团结。比如，
(
0
,
1
)
(
1
,
2
)
(0,1)(1,2)
(0,1)(1,2) 就实现了团结，而
(
0
,
1
)
(
2
,
1
)
(0,1)(2,1)
(0,1)(2,1) 和
(
0
,
0
)
(
1
,
2
)
(0,0)(1,2)
(0,0)(1,2) 都不是团结。把数合在一起的方法，是胸靠胸、背靠背、背靠胸或胸靠背。请判断世界人民能否实现大团结。如果能，请输出大团结的实现方案。
Input
第一行，一个正整数
n
n
n，表示世界上有
n
n
n 个人。
剩余
n
n
n 行，每行是用空格隔开的两个自然数，大于等于
0
0
0 且小于等于
6
6
6，第
(
i
+
1
)
(i+1)
(i+1) 行表示第
i
i
i 个人胸前和背后的数字。
Output
如大团结可以实现，输出
n
n
n ，每行两个空格隔开的数字。第一个是人的编号（同输入）；第二个是“
−
–
−”或“
+
+
+”，“
+
+
+”表示这个人胸在前，背在后，“
−
–
−”反之。人们按照你输出的顺序和面对的方向从前到后站立。具体参见样例。
如大团结不能实现，输出一行“
N
o
S
o
l
u
t
i
o
n
No\,Solution
NoSolution”（不含引号）。
Sample Input
| 5 | |
|---|---|
| 1 | 2 |
| 2 | 4 |
| 2 | 4 |
| 6 | 4 |
| 2 | 1 |
Sample Output
| 2 | – |
|---|---|
| 5 | + |
| 1 | + |
| 3 | + |
| 4 | – |
HINT
对于
100
%
100\%
100% 的数据，
1
≤
n
≤
100
1 \le n \le 100
1≤n≤100
思路
模板题，将数字看成点，人看成边，起点随便选（如最小的点）。
（样例没过，害得我调了半天，结果发现是Special Judge
…
…
）
\color{Blue}\colorbox{White}{（样例没过，害得我调了半天，结果发现是Special Judge……）}
（样例没过，害得我调了半天，结果发现是Special Judge……）
参考代码
#include <iostream>
#include <stack>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 1e2 + 5;
int n, cnt, s = INF;
int du[MAXN], e[MAXN][MAXN], a[MAXN], b[MAXN];
stack <int> st;
void dfs(int now)
{
for (int i = 0; i <= 6; ++i)
{
if (e[now][i])
{
--e[now][i];
--e[i][now];
--du[now];
--du[i];
dfs(i);
}
}
st.push(now);
}
void euler()
{
int last = st.top();
st.pop();
while (!st.empty())
{
int now = st.top();
st.pop();
for (int i = 1; i <= n; ++i)
{
if (a[i] == last && b[i] == now)
{
cout << i << " +\n";
a[i] = -INF;
b[i] = -INF;
break;
}
else if (a[i] == now && b[i] == last)
{
cout << i << " -\n";
a[i] = -INF;
b[i] = -INF;
break;
}
}
last = now;
}
}
int main()
{
cin >> n;
for (int i = 1; i <= n; ++i)
{
cin >> a[i] >> b[i];
++du[a[i]];
++du[b[i]];
s = min(s, min(a[i], b[i]));
++e[a[i]][b[i]];
++e[b[i]][a[i]];
}
for (int i = 0; i <= 6; ++i)
{
if (du[i] % 2)
{
++cnt;
if (cnt == 1)
{
s = i;
}
}
}
if (cnt != 0 && cnt != 2)
{
puts("No Solution");
return 0;
}
dfs(s);
for (int i = 0; i <= 6; ++i)
{
if (du[i])
{
puts("No Solution");
return 0;
}
}
euler();
return 0;
}
/**************************************************************
Language: C++
Result: Accepted
Time:0 ms
Memory:2224 kb
****************************************************************/