定义
1.欧拉路:从图中一个点出发遍历整张图,每条边通过且只通过一次
2.欧拉回路:起点等于终点的欧拉路
3.偶点:度为偶数的点
4.奇点:度为奇数的点
5.考察内容:判断欧拉(回)路的存在,输出欧拉(回)路的路径
判断欧拉(回)路的存在
前提:判断连通性,dfs或者并查集。
无向图:图中所有点都是偶点,则存在欧拉回路,任一点均可以成为起点和终点;只有两个奇点,则存在欧拉路,其中一个奇点是起点,另一个奇点是终点
有向图:图中所有点入度和出度均相等,则存在欧拉回路;只有一个点入度比出度大1,只有一个点出度比入度大1,剩下的点出入度均相等,则存在欧拉路
输出欧拉回路
1.随便输出一条,直接从起点跑,用栈存路径。
2.输出字典序最小的欧拉回路,如果数据规模较小,可以用邻接矩阵。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m, u, v, g[1005][1005];
int s[N], top;
void dfs(int u) {
for (int i = 1; i <= n; i ++) {
if (g[u][i]) {
g[u][i] --;
g[i][u] --;
dfs(i);
}
}
s[++ top] = u;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i ++) {
cin >> u >> v;
g[u][v] ++, g[v][u] ++;
}
dfs(1);
while (top) cout << s[top --] << " ";
return 0;
}
数据较大,就需要用类似打标记的方法标记边的遍历情况。
例题:P7771 【模板】欧拉路径
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m, u, v, del[N];
int du[N][2];//0入度,1出度
vector<int> e[N];
stack<int> st;//用于存路径
void dfs(int u) {
for (int i = del[u]; i < e[u].size(); i = del[u]) {
del[u] = i + 1;
//这样表示u这个点的前i条出边都遍历过了,下一次到u点时要从i+1条边开始
//一笔画问题,走过一条边删一条边
dfs(e[u][i]);
}
st.push(u);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i ++) {
cin >> u >> v;
e[u].push_back(v);
du[u][1] ++, du[v][0] ++;
}
//有字典序限制,用vector存图方便排序
for (int i = 1; i <= n; i ++) sort(e[i].begin(), e[i].end());
int S = 1, cnt[2] = {0, 0};
bool flag = 1;
for (int i = 1; i <= n; i ++) {
if (du[i][1] != du[i][0]) flag = 0;
if (du[i][1] - du[i][0] == 1) cnt[1] ++, S = i;
if (du[i][0] - du[i][1] == 1) cnt[0] ++;
}
//欧拉回路和欧拉路径都不存在,输出No
if ((!flag) && !(cnt[0] == cnt[1] && cnt[0] == 1)) return !printf("No");
dfs(S); //从起点开始
while (!st.empty()) printf("%d ", st.top()), st.pop();//输出路径
return 0;
}
标签:int,出度,dfs,++,回路,欧拉
From: https://www.cnblogs.com/YHxo/p/16849049.html