题目大意
给定一个无向图，要求找到一条路径，经过每条边恰好一次，并且输出字典序最小的路径。
解题思路
这道题的本质是求欧拉路径或欧拉回路。
欧拉路径/回路的判定
对于无向图，存在一条经过每条边恰好一次的路径（欧拉路径）的充要条件是：
- 图是连通的（忽略孤立点）；
- 奇度顶点（度数为奇数的点）的个数为 0 或 2。
- 如果奇度顶点个数为 0，则存在欧拉回路，可以从任意顶点出发并回到该点。
- 如果奇度顶点个数为 2，则必须从一个奇度顶点出发，在另一个奇度顶点结束。
算法步骤
-
建图
用邻接矩阵存储图，因为题目中节点编号范围不大（最大 500），适合用矩阵存储边的数量。 -
统计度数
记录每个节点的度数，用于判断欧拉路径的起点。 -
确定起点
- 如果存在奇度顶点，则从最小的奇度顶点开始搜索。
- 否则（所有点度数均为偶数），从最小的节点开始搜索。
-
DFS 搜索路径
从起点开始，按照节点编号从小到大的顺序遍历每条边，找到一条边就继续 DFS。每次递归结束后将当前节点加入路径。 -
输出路径
最终得到的路径是逆序的，需要反转后输出。
代码实现
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
const int N = 1e5 + 10, mod = 998244353, inf = 0x3f3f3f3f;
ll n, u, v, ans[1500], idx = 0;
ll line[555][555], du[555];
ll mn = 1e9, mx = 0;void dfs(int x) {for (int i = 1; i <= mx; i++) { //从小到大遍历 让ans值尽量小if (line[x][i]) {line[i][x]--;line[x][i]--;dfs(i);}}ans[++idx] = x;
}void solve() {cin >> n;for (int i = 1; i <= n; i++) {cin >> u >> v;line[u][v]++;line[v][u]++;du[u]++;du[v]++;// 记录度数mx = max(mx, max(u, v));mn = min(mn, min(u, v));}ll start = mn; // 初始化为最小编号 如果找不到奇度编号 就从最小的开始搜for (int i = 1; i <= mx; i++) { // 找最小的奇度编号（因为题目要求从小输出）if (du[i] % 2) {start = i;break;}}dfs(start);for (int i = idx; i >= 1; i--) // 倒序输出 因为ans先记录后面的数cout << ans[i] << '\n';
}
int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int _ = 1;cin >> _;while (_--) {solve();}return 0;
}