一笔画问题
【题目描述】
如果一个图存在一笔画，则一笔画的路径叫做欧拉路，如果最后又回到起点，那这个路径叫做欧拉回路。
根据一笔画的两个定理，如果寻找欧拉回路，对任意一个点执行深度优先遍历；找欧拉路，则对一个奇点执行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; }