目录
- 1 介绍
- 2 训练
1 介绍
本专题用来记录欧拉回路和欧拉路径相关的题目。
相关结论：
（1）对于无向图，所有边都是连通的。
（1.1）存在欧拉路径的充要条件：度数为奇数的结点只能是0个或者2个。
（1.2）存在欧拉回路的充要条件：度数为奇数的结点只能是0个。
（2）对于有向图，所有边都是连通的。
（2.1）存在欧拉路径的充要条件1：所有结点的出度均等于其入度。
（2.1）存在欧拉路径的充要条件2：除去两个结点外，其余所有结点的出度等于入度。且除去的那两个结点，其中一个结点的出度比入度多1（起点），另一个结点的入度比出度多1（终点）。
（2.2）存在欧拉回路的充要条件：所有结点的出度均等于其入度。
2 训练
题目1：1123铲雪车
C++代码如下，
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int main() {
double x1, y1, x2, y2;
cin >> x1 >> y1;
double sum = 0;
while (cin >> x1 >> y1 >> x2 >> y2) {
double dx = x1 - x2;
double dy = y1 - y2;
sum += sqrt(dx * dx + dy * dy) * 2;
}
int minutes = round(sum / 1000 / 20 * 60);
int hours = minutes / 60;
minutes %= 60;
printf("%d:%02d\n", hours, minutes);
return 0;
}
题目2：1184欧拉回路
C++代码如下，
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010, M = 400010;
int type;
int n, m;
int h[N], e[M], ne[M], idx;
bool used[M];
int ans[M], cnt;
int din[N], dout[N];
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u) {
for (int &i = h[u]; ~i;) {
if (used[i]) {
i = ne[i];
continue;
}
used[i] = true;
if (type == 1) used[i ^ 1] = true;
int t;
if (type == 1) {
t = i / 2 + 1;
if (i & 1) t = -t;
} else {
t = i + 1;
}
int j = e[i];
i = ne[i];
dfs(j);
ans[++cnt] = t;
}
}
int main() {
scanf("%d", &type);
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
for (int i = 0; i < m; ++i) {
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
if (type == 1) add(b, a);
din[b]++, dout[a]++;
}
if (type == 1) {
for (int i = 1; i <= n; ++i) {
if (din[i] + dout[i] & 1) {
puts("NO");
return 0;
}
}
} else {
for (int i = 1; i <= n; ++i) {
if (din[i] != dout[i]) {
puts("NO");
return 0;
}
}
}
for (int i = 1; i <= n; ++i) {
if (h[i] != -1) {
dfs(i);
break;
}
}
if (cnt < m) {
puts("NO");
return 0;
}
puts("YES");
for (int i = cnt; i; --i) printf("%d ", ans[i]);
puts("");
return 0;
}
题目3：1124骑马修栅栏
C++代码如下，
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 510;
int n = 500, m;
int g[N][N];
int ans[1100], cnt;
int d[N];
void dfs(int u) {
for (int i = 1; i <= n; ++i) {
if (g[u][i]) {
g[u][i]--, g[i][u]--;
dfs(i);
}
}
ans[++cnt] = u;
}
int main() {
cin >> m;
while (m--) {
int a, b;
cin >> a >> b;
g[a][b]++, g[b][a]++;
d[a]++, d[b]++;
}
int start = 1;
while (!d[start]) start++;
for (int i = 1; i <= n; ++i) {
if (d[i] % 2) {
start = i;
break;
}
}
dfs(start);
for (int i = cnt; i; i--) printf("%d\n", ans[i]);
return 0;
}
题目4：1185单词游戏
C++代码如下，
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 30;
int n;
int din[N], dout[N], p[N];
bool st[N];
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main() {
char str[1010];
int T;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
memset(din, 0, sizeof din);
memset(dout, 0, sizeof dout);
memset(st, 0, sizeof st);
for (int i = 0; i < 26; ++i) p[i] = i;
for (int i = 0; i < n; ++i) {
scanf("%s", str);
int len = strlen(str);
int a = str[0] - 'a', b = str[len - 1] - 'a';
st[a] = st[b] = true;
dout[a]++, din[b]++;
p[find(a)] = find(b);
}
int start = 0, end = 0;
bool success = true;
for (int i = 0; i < 26; ++i) {
if (din[i] != dout[i]) {
if (din[i] == dout[i] + 1) end++;
else if (din[i] + 1 == dout[i]) start++;
else {
success = false;
break;
}
}
}
if (success && !(!start && !end || start == 1 && end == 1)) success = false;
int rep = -1;
for (int i = 0; i < 26; ++i) {
if (st[i]) {
if (rep == -1) rep = find(i);
else if (rep != find(i)) {
success = false;
break;
}
}
}
if (success) puts("Ordering is possible.");
else puts("The door cannot be opened.");
}
return 0;
}
