一笔画问题
【题目描述】
如果一个图存在一笔画，则一笔画的路径叫做欧拉路，如果最后又回到起点，那这个路径叫做欧拉回路。
根据一笔画的两个定理，如果寻找欧拉回路，对任意一个点执行深度优先遍历；找欧拉路，则对一个奇点执行dfs，时间复杂度为O(m+n)，m为边数，n是点数。
【输入】
第一行n，m，有n个点，m条边，以下m行描述每条边连接的两点。
【输出】
欧拉路或欧拉回路,输出一条路径即可。
【输入样例】
5 5 1 2 2 3 3 4 4 5 5 1
【输出样例】
1 5 4 3 2 1
【提示】
【数据范围】
对于100%的数据：1 < n < 100,1 < m < 2000。
【知识补充】
欧拉路与欧拉回路判定条件
对于无向图：
欧拉回路（回到起点）：
所有顶点的度数均为偶数。
图是连通的（边集非空且能通过边到达所有边相关的顶点）。
欧拉路（不要求回到起点）：
恰好有两个顶点的度数为奇数（起点和终点），其余均为偶数。
图是连通的。
【思路】
读入图，统计每个点的度数。
检查奇数度顶点的个数：
0 个：欧拉回路，任选一个（有边的）起点。
2 个：欧拉路，选一个奇数度点作为起点。
其他：无欧拉路/回路（但题目保证存在）。
找欧拉路径：
从起点 DFS，每次选择一条未访问的边，递归后把点加入路径。
最后逆序输出路径。
【参考答案】
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
const int MAXN = 105; // 最大点数，
const int MAXM = 2005; // 最大边数，
int n, m; // 实际点数和边数
int deg[MAXN]; // 存储每个顶点的度数
int G[MAXN][MAXN]; // 邻接矩阵存储图，G[u][v] 表示 u 到 v 的边数（处理重边）
vector<int> path; // 存储最终的欧拉路径
//深搜找欧拉路径
void dfs(int u) {
// 遍历所有可能的邻接点
for (int v = 1; v <= n; v++) {
// 如果 u 到 v 还有未访问的边
if (G[u][v] > 0) {
// 删除这条边（无向图要删除两个方向）
G[u][v]--;
G[v][u]--;
// 递归访问下一个顶点
dfs(v);
// 注意：这里没有立即将顶点加入路径，
// 而是在递归返回后才加入，这是关键
}
}
// 当 当前顶点的所有边都处理完后，将顶点加入路径
// 这样保证路径是逆序构建的
path.push_back(u);
}
int main() {
cin >> n >> m; // 读入点数和边数
// 读入每条边并构建图
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
// 在邻接矩阵中记录边（无向图）
G[u][v]++;
G[v][u]++;
// 更新顶点的度数
deg[u]++;
deg[v]++;
}
// 寻找欧拉路径的起点
int start = 1; // 默认从顶点1开始（用于欧拉回路情况）
// 检查是否存在奇数度顶点（欧拉路情况）
for (int i = 1; i <= n; i++) {
if (deg[i] % 2 == 1) {
// 找到第一个奇数度顶点作为起点（欧拉路必须从奇数度顶点开始）
start = i;
break; // 只需要找到一个奇数度顶点即可
}
}
// 如果没有奇数度顶点，说明是欧拉回路，start保持为1
// 找欧拉路径
dfs(start);
// 输出路径
// 由于路径是逆序存储的，需要从后往前输出
for (int i = path.size() - 1; i >= 0; i--) {
cout << path[i];
if (i > 0) cout << " "; // 最后一个数后面不加空格
}
cout << endl;
return 0;
}扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。
