欧拉路径：从某结点出发一笔画成所经过的路线
欧拉回路：在欧拉路径的基础上又回到起点
1、对于无向连通图
（1）存在欧拉路径的充分必要条件是：度数为奇数的点只能有0个或2个
（2）存在欧拉回路的充分必要条件是：不存在度数为奇数的点
2、对于有向连通图
（1）存在欧拉路径的充分必要条件是：除起点和终点外所有点入度均等于出度，同时要么起点出度比入度多1且终点入度比出度多1，要么起点与终点的入度与出度均相等
（2）存在欧拉回路的充分必要条件是：所有点出度均等于入度
求任意欧拉回路，记录并输出边的编号（链式前向星存图）
#include <bits/stdc++.h>
using ll = long long;
constexpr int N = 1e5 + 5, M = 4e5 + 5;;
int type;
int h[N], e[M], ne[M], idx;
int n, m;
int ans[M];
bool used[M];
int din[N], dout[N];
int cnt;
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
int main () {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
memset(h, -1, sizeof h);
std::cin >> type;
std::cin >> n >> m;
for (int i = 0; i < m; i ++) {
int a, b;
std::cin >> 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) {
std::cout << "NO\n";
return 0;
}
}
} else {
for (int i = 1; i <= n; i ++) {
if (din[i] != dout[i]) {
std::cout << "NO\n";
return 0;
}
}
}
std::function<void(int)> 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;
}
};
for (int i = 1; i <= n; i++) {
if (~h[i]) {
dfs(i);
break;
}
}
if (cnt < m) {
std::cout << "NO\n";
} else {
std::cout << "YES\n";
for (int i = cnt; i >= 1; i --) {
std::cout << ans[i] << " \n"[i == 1];
}
}
return 0;
}
/*
*/
记得删完边再遍历
无向图求最小字典序的欧拉路径
#include <bits/stdc++.h>
using ll = long long;
int main () {
std::ios::sync_with_stdio(0); std::cin.tie(0);
int m, n = 500;
std::cin >> m;
std::vector g(n, std::vector(n, 0));
std::vector<int> d(n);
for (int i = 0; i < m; i ++) {
int u, v;
std::cin >> u >> v;
u --, v --;
g[u][v] ++, g[v][u] ++;
d[u] ++, d[v] ++;
}
int start = -1;
for (int i = 0; i < n; i ++) {
if (start == -1 && d[i]) {
start = i;
}
if (d[i] & 1) {
start = i;
break;
}
}
int cnt = 0;
std::vector<int> ans;
std::function<void(int)> dfs = [&](int u) {
for (int i = 0; i < n; i ++) {
if (g[u][i]) {
g[u][i] --, g[i][u] --;
dfs(i);
}
}
ans.push_back(u + 1);
};
dfs(start);
for (int i = ans.size() - 1; ~i; i --) {
std::cout << ans[i] << "\n";
}
return 0;
}
求有向图字典序最小欧拉路径
P7771 【模板】欧拉路径 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include <bits/stdc++.h>
using ll = long long;
int main () {
std::ios::sync_with_stdio(0); std::cin.tie(0);
int n, m;
std::cin >> n >> m;
std::vector<int> g[n], din(n), dout(n);
for (int i = 0; i < m; i ++) {
int a, b;
std::cin >> a >> b;
a --, b --;
g[a].push_back(b);
dout[a] ++, din[b] ++;
}
for (int i = 0; i < n; i ++) {
sort(g[i].begin(), g[i].end());
}
int start = -1, st = 0, ed = 0;
bool ok = true;
for (int i = 0; i < n; i ++) {
if (din[i] != dout[i]) {
if (abs(din[i] - dout[i]) > 1) {
ok = false;
break;
} else if (din[i] == dout[i] + 1) {
ed ++;
} else {
st ++, start = i;
}
}
}
if (st != ed || st > 1 || ed > 1) {
ok = false;
}
if (!ok) {
std::cout << "No\n";
return 0;
}
std::vector<int> ans;
std::vector<int> del(n);
std::function<void(int)> dfs = [&](int u) {
for (int i = del[u]; i < g[u].size(); i = del[u]) {
del[u] = i + 1;
dfs(g[u][i]);
}
ans.push_back(u + 1);
};
if (start != -1) {
dfs(start);
} else {
for (int i = 0; i < n; i ++) {
if (g[i].size()) {
dfs(i);
break;
}
}
}
std::reverse(ans.begin(), ans.end());
if (m != ans.size() - 1) {
std::cout << "No\n";
} else {
for (int x : ans) std::cout << x << " ";
std::cout << "\n";
}
return 0;
}
有向图判断是否存在欧拉回路
#include <bits/stdc++.h>
using ll = long long;
struct DSU {
std::vector<int> f, siz;
DSU(int n) : f(n), siz(n, 1) { iota(f.begin(), f.end(), 0); }
int leader(int x) {
while (x != f[x]) x = f[x] = f[f[x]];
return x;
}
bool same(int x, int y) { return leader(x) == leader(y); }
bool merge(int x, int y) {
x = leader(x);
y = leader(y);
if (x == y) return false;
siz[x] += siz[y];
f[y] = x;
return true;
}
int size(int x) { return siz[leader(x)]; }
};
int main () {
std::ios::sync_with_stdio(0); std::cin.tie(0);
int tt;
std::cin >> tt;
while (tt --) {
int n;
std::cin >> n;
std::string s;
DSU g(30);
std::vector<bool> st(30);
std::vector<int> din(30), dout(30);
int cnt = 0;
for (int i = 0; i < n; i ++) {
std::cin >> s;
int a = s[0] - 'a', b = s.back() - 'a';
g.merge(a, b);
dout[a] ++, din[b] ++;
if (!st[a]) {
st[a] = true;
cnt ++;
}
if (!st[b]) {
st[b] = true;
cnt ++;
}
}
bool ok = true;
int start = 0, ed = 0;
for (int i = 0; i < 26; i ++) {
if (st[i] && g.size(i) != cnt) { //判断连通性
ok = false;
break;
}
if (st[i]) { //判断是否满足有向图存在欧拉回路的条件
if (abs(din[i] - dout[i]) > 1) {
ok = false;
} else if (din[i] == dout[i] + 1) {
ed ++;
} else if (din[i] + 1 == dout[i]) {
start ++;
}
}
}
if (start != ed || start > 1 || ed > 1) {
ok = false;
}
if (ok) {
std::cout << "Ordering is possible.\n";
} else {
std::cout << "The door cannot be opened.\n";
}
}
return 0;
}
有向图按边来寻找字典序最小欧拉环路（暴力写法）
P1127 词链 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include <bits/stdc++.h>
using ll = long long;
constexpr int N = 1100;
struct DSU {
std::vector<int> f, siz;
DSU(int n) : f(n), siz(n, 1) { iota(f.begin(), f.end(), 0); }
int leader(int x) {
while (x != f[x]) x = f[x] = f[f[x]];
return x;
}
bool same(int x, int y) { return leader(x) == leader(y); }
bool merge(int x, int y) {
x = leader(x);
y = leader(y);
if (x == y) return false;
siz[x] += siz[y];
f[y] = x;
return true;
}
int size(int x) { return siz[leader(x)]; }
};
struct node {
int x, y;
}e[N];
int idx;
void add(int a, int b) {
e[idx ++] = {a, b};
}
int main () {
std::ios::sync_with_stdio(0); std::cin.tie(0);
int n;
std::cin >> n;
std::vector<std::string> g(n);
std::vector<int> din(30), dout(30);
for (int i = 0; i < n; i ++) {
std::cin >> g[i];
}
sort(g.begin(), g.end());
int cnt = 0;
std::vector<bool> st(30);
DSU G(30);
int now = g[0][0] - 'a';
for (int i = 0; i < n; i ++) {
int a = g[i].front() - 'a';
int b = g[i].back() - 'a';
add(a, b);
din[b] ++, dout[a] ++;
G.merge(a, b);
if (!st[a]) {
st[a] = true;
cnt ++;
}
if (!st[b]) {
st[b] = true;
cnt ++;
}
}
bool ok = true;
int start = 0, ed = 0;
for (int i = 0; i < 26; i ++) {
if (st[i] && G.size(i) != cnt) {
ok = false;
break;
}
if (st[i]) {
if (abs(din[i] - dout[i]) > 1) {
ok = false;
} else if (din[i] == dout[i] + 1) {
ed ++;
} else if (din[i] + 1 == dout[i]) {
start ++, now = i;
}
}
}
if (start != ed || start > 1 || ed > 1) {
ok = false;
}
if (!ok) {
std::cout << "***\n";
return 0;
}
std::vector<std::string> ans;
std::vector<bool> used(n);
std::function<void(int)> dfs = [&](int now) {
for (int i = 0; i < idx; i ++) {
if (!used[i] && g[i][0] - 'a' == now) {
used[i] = true;
dfs(g[i].back() - 'a');
ans.push_back(g[i]);
}
}
};
dfs(now);
for (int i = ans.size() - 1; ~i; i --) {
std::cout << ans[i] << ".\n"[i == 0];
}
return 0;
}
因为这题的结点最多只有26个，所以可以直接给字符串排序一下，然后从前往后找第一个没有打上过标记的字符串
判断欧拉回路是否存在则是用并查集以及欧拉回路的性质来判断
dfs从起点开始，起点要么是字典序最小的字母，要么是奇数度数的点