欧拉回路欧拉路径

admin 管理员组

文章数量: 888297

欧拉回路/欧拉路径

搬来大佬的前置知识：
定义：从一个点出发，不重不漏的经过图中每一条边的一条路径（允许多次经过同一个点）。如果此路径的起点和终点相同，则称其为一条欧拉回路。
欧拉路径判定（是否存在）：
首先要保证连通

• 有向图欧拉路径：图中恰好存在 1 1 1 个点出度比入度多 1 1 1（这个点即为起点 S S S）， 1 1 1 个点入度比出度多 1 1 1（这个点即为终点 T T T），其余节点出度 = = = 入度。
• 有向图欧拉回路：所有点的入度 = = = 出度（起点 S S S 和终点 T T T 可以为任意点）。
• 无向图欧拉路径：图中恰好存在 2 2 2 个点的度数是奇数，其余节点的度数为偶数，这两个度数为奇数的点即为欧拉路径的 起点 S S S 和 终点 T T T。
• 无向图欧拉回路：所有点的度数都是偶数（起点 S S S 和终点 T T T 可以为任意点）。

注：存在欧拉回路（即满足存在欧拉回路的条件），也一定存在欧拉路径。
当然，一副图有欧拉路径，还必须满足将它的有向边视为无向边后它是连通的（不考虑度为 0 0 0 的孤立点），连通性的判断我们可以使用并查集或 d f s dfs dfs

求欧拉路径的 H i e r h o l z e r Hierholzer Hierholzer 算法流程：
开始递归函数 d f s ( x ) dfs(x) dfs(x)
循环寻找与 x x x 相连的边 x → u x \to u x→u:
删除 x → u x \to u x→u
删除 u → x u \to x u→x
d f s ( u ) dfs(u) dfs(u)
s t . p u s h ( u ) st.push(u) st.push(u)，存欧拉路径

P7771 【模板】欧拉路径
题意：
有向图欧拉路径
思路：
大佬博客
由于本题保证将有向边视为无向边后图连通，所以本题不用判断
首先根据度数判定是否存在欧拉路径
如果存在就从起点 s s s 开始遍历
求欧拉路径 H i e r h o l z e r Hierholzer Hierholzer 需要删边
有向图中比较好的办法是开一个 d e l del del 数组
d e l [ x ] del[x] del[x] 表示 e [ x ] [ 1 , 2 … … , d e l [ x ] − 1 ] e[x][1,2……,del[x]-1] e[x][1,2……,del[x]−1] 都已经被标记访问过，下一次要从 e [ x ] [ d e l [ x ] ] e[x][del[x]] e[x][del[x]] 开始访问
本题还要求输出字典序最小的欧拉路径，比较简单的办法就是用 v e c t o r vector vector 存边，然后 s o r t sort sort
然后用栈或队列存一下遍历顺序最后输出就好了
复杂度 O ( n + m l o g m ) O(n+mlogm) O(n+mlogm)
code：

#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define ld long double
#define all(x) x.begin(), x.end()
#define mem(x, d) memset(x, d, sizeof(x))
#define eps 1e-6
using namespace std;
const int maxn = 1e5 + 9;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll n, m;
vector <int> e[maxn];
int deg[maxn][2];// 0入度，1出度 
stack <int> st;
int del[maxn];void dfs(int x){for(int i = del[x]; i < e[x].size(); i = del[x]){del[x] = i + 1;dfs(e[x][i]);}st.push(x);
}
void work()
{cin >> n >> m;for(int i = 1, x, y; i <= m; ++i){cin >> x >> y;e[x].push_back(y);deg[x][1]++;deg[y][0]++;}for(int i = 1; i <= n; ++i) sort(all(e[i]));bool f = 0;// 判断是否为欧拉回路int s = 1, cnt[2] = {0};for(int i = 1; i <= n; ++i){if(deg[i][0] != deg[i][1]) f = 1;if(deg[i][1] - deg[i][0] == 1) ++cnt[1], s = i;if(deg[i][0] - deg[i][1] == 1) ++cnt[0];}if(f && !(cnt[0] == cnt[1] && cnt[0] == 1)){//不满足欧拉回路的判定条件，也不满足欧拉路径的判定条件cout << "No";return;}dfs(s);while(!st.empty()) {cout << st.top() << " ";st.pop();} 
}int main()
{ios::sync_with_stdio(0);
//	int TT;cin>>TT;while(TT--)work();return 0;
}

P1341 无序字母对
题意：
无向图欧拉路径
思路：
无向图用 H i e r h o l z e r Hierholzer Hierholzer 求欧拉路径，开邻接矩阵删边比较方便
每读入两个字母就给这两个字母连一条无向边，先判定是否连通，然后判定是否存在欧拉路径或者欧拉回路
注意如果存在欧拉回路，起点设为字典序最小的点就好了
然后求欧拉路径输出
code：

#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define ld long double
#define all(x) x.begin(), x.end()
#define mem(x, d) memset(x, d, sizeof(x))
#define eps 1e-6
using namespace std;
const int maxn = 2e2 + 9;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll n, m;
int deg[maxn];
int f[maxn];
int mp[maxn][maxn];
stack <int> st;int find(int x){return f[x] == x ? x : f[x] = find(f[x]);
}
void merge(int x, int y){x = find(x); y = find(y);if(x != y){f[x] = y;		}
}
void dfs(int x){for(int i = 1; i <= maxn - 9; ++i) if(mp[x][i]){mp[x][i]--;mp[i][x]--;dfs(i);}st.push(x);
}
void work()
{cin >> n;for(int i = 1; i <= n; ++i){char x, y;cin >> x >> y;deg[x]++;deg[y]++;mp[x][y]++;// 可能有重边mp[y][x]++;merge(x, y);}set <int> se;for(int i = 1; i <= maxn - 9; ++i) if(deg[i])se.insert(find(i));if(se.size() != 1){cout << "No Solution\n";return;}int a = 0, b = 0, s = -1;for(int i = 1; i <= maxn - 9; ++i){if(!deg[i]) continue;if(deg[i] & 1) {++a;if(s == -1) s = i;}else ++b;}if(a && (a != 2)){cout << "No Solution\n";return;}if(s == -1){for(int i = 1; i <= maxn - 9; ++i) if(deg[i]){s = i;break;}}dfs(s);while(!st.empty()){cout << char(st.top());st.pop();}
}
int main()
{ios::sync_with_stdio(0);
//	int TT;cin>>TT;while(TT--)work();return 0;
}

P2731 [USACO3.3]骑马修栅栏 Riding the Fences
思路：
无向图求欧拉路径
本题有重边
因为算法要删边
因此存边代码应该写成

mp[x][y]++; mp[y][x]++;

而不是

mp[x][y] = mp[y][x] = 1;

删边代码同理
code：

#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define ld long double
#define all(x) x.begin(), x.end()
#define mem(x, d) memset(x, d, sizeof(x))
#define eps 1e-6
using namespace std;
const int maxn = 5e2 + 9;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll n, m;
int deg[maxn];
int mp[maxn][maxn];
stack <int> st;void dfs(int x){for(int i = 1; i <= maxn - 9; ++i) if(mp[x][i] >= 1){mp[x][i]--;mp[i][x]--;dfs(i);}st.push(x);
}
void work()
{cin >> n;for(int i = 1; i <= n; ++i){int x, y;cin >> x >> y;deg[x]++;deg[y]++;mp[x][y]++;mp[y][x]++;}int s = 1;for(int i = 1; i <= maxn - 9; ++i) if(deg[i] & 1){s = i;break;}dfs(s);while(!st.empty()){cout << st.top() << endl;st.pop();}
}int main()
{ios::sync_with_stdio(0);
//	int TT;cin>>TT;while(TT--)work();return 0;
}

本文标签： 欧拉回路欧拉路径