欧拉路
title: 欧拉路
categories:
- ICPC
tags:
- null
abbrlink: cad745f
date: 2023-12-10 00:00:00
欧拉路
2018的国家集训队论文《欧拉图相关的生成与计数问题探究》
[Tricks] 记各类欧拉回路问题 - 樱雪喵 - 博客园
欧拉路径是满足恰经过所有边一次的通路
- 欧拉回路是起点和终点相同的一条欧拉路径.
判别法则:
- 有向图存在欧拉回路: G中所有度数非0的点是强连通的,且所有点入度均等于出度.
- 有向图存在欧拉通路:
- 将边看成无向边后,G中所有度数非0的点是连通的。
- 最多只有一个点入度比出度大 1,作为欧拉通路的起点
- 最多只有一个点出度比入度大 1,作为欧拉通路的终点
- 其他所有点入度均等于出度
- 无向图存在欧拉回路: G中所有度数非0的点是连通的且所有点度数均为偶数.
- 无向图存在欧拉通路: G中所有度数非0的点是连通。并且G中恰好存在0或2个奇度点。 其他所有点度数均为偶数。那两个奇度点中, 一个作为欧拉通路之起点, 另一个作为终点.
算法流程:感性理解:先找一条起点到终点的通路,然后不断回溯找环。
先用充要条件也就是度数和连通性去判断是不是存在欧拉路 ,存在的话用dfs构造欧拉路。
有向图最小字典序欧拉路https://www.luogu.com.cn/problem/P7771
- 当前弧优化保证时间复杂度$O(n+m)$
void solve() {
int n, m;
cin >> n >> m;
vector<int> din(n + 1), dout(n + 1);
vector<int> path;
vector<vector<int>> e(n + 1);
vector<int> cur(n + 1);
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
e[u].push_back(v);
din[v]++;
dout[u]++;
}
for (int i = 1; i <= n; i++) sort(alls(e[i]));
function<void(int)> dfs = [&](int u) {
int sz = e[u].size();
while (cur[u] < sz) {
int v = e[u][cur[u]];
cur[u]++;
dfs(v);
path.push_back(v);
}
};
auto euler_dir = [&]() {
int x = 0, y = 0, z = 0;
for (int i = 1; i <= n; i++) {
if (din[i] + 1 == dout[i]) {
x = i;
y++;
}
if (din[i] != dout[i])
z++;
}
bool flag = ((y == 1 && z == 2) || (z == 0));
if (flag == 0)
return false;
if (x == 0) {
for (int i = 1; i <= n; i++)
if (din[i]) {
x = i;
break;
}
}
dfs(x);
path.push_back(x);
if ((int)path.size() != m + 1)
return false;
reverse(alls(path));
return true;
};
if (euler_dir()) {
for (auto x : path) cout << x << " ";
} else {
cout << "No" << endl;
}
}
无向图最小字典序欧拉路:寻找起点的时候保证起点是最小的
struct node {
int v, idx;
bool operator<(const node &other) {
return v < other.v;
}
};
void solve() {
int n = 500, m;
cin >> m;
vector<int> deg(n + 1);
vector<int> cur(n + 1);
vector<bool> vis(2 * m + 10);
int cnt = 1;
vector<vector<node>> e(n + 1);
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
deg[u]++;
deg[v]++;
cnt++;
e[u].push_back({v, cnt});
cnt++;
e[v].push_back({u, cnt});
}
for (int i = 1; i <= n; i++) sort(alls(e[i]));
vector<int> path;
function<void(int)> dfs = [&](int u) {
int sz = e[u].size();
while (cur[u] < sz) {
auto [v, idx] = e[u][cur[u]];
if (vis[idx] == 0) {
vis[idx] = vis[idx ^ 1] = true;
cur[u]++;
dfs(v);
path.push_back(v);
} else {
cur[u]++;
}
}
};
auto euler = [&]() {
int x = 0, y = 0; // 保证字典序最小
for (int i = n; i >= 1; i--) {
if (deg[i] & 1) {
x = i;
y++;
}
}
if (y > 0 && y != 2)
return false;
if (x == 0) {
for (int i = 1; i <= n; i++) {
if (deg[i]) {
x = i;
break;
}
}
}
dfs(x);
path.push_back(x);
if ((int)path.size() != m + 1)
return false;
reverse(alls(path));
return true;
};
if (euler()) {
for (auto x : path) cout << x << endl;
} else {
cout << "NO" << endl;
}
}
无向图欧拉回路:正向边输出边的编号,反向边输出相反数
struct node {
int v, idx, res, op;
//idx是每个方向边编号,res是无向边共用的编号,op表示正边反边
bool operator<(const node &other) {
return v < other.v;
}
};
// 只找欧拉回路
void solve1() { // 无向图
int n, m;
cin >> n >> m;
vector<int> deg(n + 1);
vector<int> cur(n + 1);
vector<bool> vis(2 * m + 10);
int cnt = 1;
vector<vector<node>> e(n + 1);
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
deg[u]++;
deg[v]++;
cnt++;
e[u].push_back({v, cnt, i, 1});
cnt++;
e[v].push_back({u, cnt, i, 2});
}
vector<int> path;
function<void(int)> dfs = [&](int u) {
int sz = e[u].size();
while (cur[u] < sz) {
auto [v, idx, res, op] = e[u][cur[u]];
if (vis[idx] == 0) {
vis[idx] = vis[idx ^ 1] = true;
cur[u]++;
dfs(v);
if (op == 1)
path.push_back(res);
else
path.push_back(-res);
} else {
cur[u]++;
}
}
};
auto euler = [&]() {
int x = 0, y = 0; // 保证字典序最小
for (int i = n; i >= 1; i--) {
if (deg[i] & 1) {
x = i;
y++;
}
}
if (y > 0)
return false;
if (x == 0) {
for (int i = 1; i <= n; i++) {
if (deg[i]) {
x = i;
break;
}
}
}
dfs(x);
// path.push_back(x);
if ((int)path.size() != m)
return false;
reverse(alls(path));
return true;
};
if (euler()) {
cout << "YES" << endl;
for (auto x : path) cout << x << " ";
} else {
cout << "NO" << endl;
}
}
有向图欧拉回路:输出路径的边的编号
struct node2 {
int v, id;
};
void solve2() { // 有向
int n, m;
cin >> n >> m;
vector<int> din(n + 1), dout(n + 1);
vector<int> path;
vector<vector<node2>> e(n + 1);
vector<int> cur(n + 1);
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
e[u].push_back({v, i});
din[v]++;
dout[u]++;
}
function<void(int)> dfs = [&](int u) {
int sz = e[u].size();
while (cur[u] < sz) {
auto [v, res] = e[u][cur[u]];
cur[u]++;
dfs(v);
path.push_back(res);
}
};
auto euler_dir = [&]() {
int x = 0, y = 0, z = 0;
for (int i = 1; i <= n; i++) {
if (din[i] + 1 == dout[i]) {
x = i;
y++;
}
if (din[i] != dout[i])
z++;
}
bool flag = (z == 0);
if (flag == 0)
return false;
if (x == 0) {
for (int i = 1; i <= n; i++)
if (din[i]) {
x = i;
break;
}
}
dfs(x);
// path.push_back(x);
if ((int)path.size() != m)
return false;
reverse(alls(path));
return true;
};
if (euler_dir()) {
cout << "YES" << endl;
for (auto x : path) cout << x << " ";
} else {
cout << "NO" << endl;
}
}
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 爱飞鱼的blog!