Submission #68155125

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int N=3e5+10;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
map<int,int> mp;
int n,m,k;
int a[N],b[N];
void slove(){
    int x,y;
    cin>>n>>m>>x>>y;
    vector<int> vis(n+1,0);
    vector<vector<int>> q(n+1);
    for(int i=1;i<=m;i++){
        int u,v;cin>>u>>v;
        q[u].push_back(v);
        q[v].push_back(u);
    }
    vector<int> ans;
    auto dfs=[&](auto &&self,int u)->int{
        vis[u]=1;
        if(u==y){
            return 1;
        }
        priority_queue<int,vector<int>,greater<int>> p;
        for(auto t:q[u]){
            if(vis[t]) continue;
            p.push(t);
        }
        if(p.empty()) return 0;
        while(!p.empty()){
            int v=p.top();
            p.pop();
            if(self(self,v)==1){
                ans.push_back(v);
                return 1;
            }
        }
        return 0;
    };
    vis[x]=1;
    dfs(dfs,x);
    ans.push_back(x);
    for(int i=ans.size()-1;i>=0;i--){
        cout<<ans[i]<<' ';
    }cout<<endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
    int T=1;
    cin>>T;
    while(T--){
        slove();
    }
}

Submission Info

Judge Result