题解：AT_abc417_e A Path in A Dictionary

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e3 + 5;
int T, n, m, s, t, tot, ans[N];

bool vis[N], f;
vector <int> G[N];
// tot 是最后记录路径长度
// ans 是用来记录路径的
// vis 是当前点是否访问过
// f 是 dfs 中标记终点是否已经走到过

void dfs(int u, int st){
    // st 是当前遍历到的点 u 在路径中的位置
	vis[u] = 1;
	ans[st] = u;
	if(u == t){
		tot = st;
        // 因为我是在主函数中输出，所以需要令开一个 tot 记录路径长度
        // 你可以在这里直接输出，这就不需要 tot 这个变量了
		f = 1; // 标记终点已经访问过
		return;
	}
	for(int v : G[u]){
		if(vis[v]) continue; // 题目要求路径上不能有重复的点
		dfs(v, st + 1);
		if(f) return;
        // 如果已经访问过终点，就已经找到答案，那么就不用继续 dfs 了
	}
}

int main(){
	
	ios :: sync_with_stdio(false);
	cin >> T;
	while(T--){
		cin >> n >> m >> s >> t;
		for(int i = 1, u, v; i <= m; i++)
			cin >> u >> v, G[u].emplace_back(v), G[v].emplace_back(u);
		for(int i = 1; i <= n; i++)
			sort(G[i].begin(), G[i].end()); // 排序以满足字典序要求
		f = 0;
		dfs(s, 1);
		for(int i = 1; i <= tot; i++) cout << ans[i] << ' ';
		cout << '\n';
		for(int i = 1; i <= n; i++) G[i].clear(), vis[i] = 0; // 多测清空
	}
	
	return 0;
}