Submission #68156289

---

Source Code Expand

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

void solve() {
    int n, m, x, y;
    cin >> n >> m >> x >> y, x--, y--;
    vector<vector<int>> grf(n);
    for (int i = 0, u, v; i < m; i++) cin >> u >> v, u--, v--, grf[u].push_back(v), grf[v].push_back(u);
    for (auto &adj : grf) sort(adj.begin(), adj.end());
    vector<bool> vis(n);
    vis[x] = true;
    vector<int> ans = {x};
    int now = x;

    auto reach = [&](int s, int t) {
        if (vis[s]) return false;
        if (s == t) return true;
        vector<bool> see(n);
        queue<int> q;
        q.push(s), see[s] = true;
        while (!q.empty()) {
            int now = q.front();
            q.pop();
            for (int to : grf[now]) {
                if (see[to] || vis[to]) continue;
                if (to == t) return true;
                see[to] = true, q.push(to);
            }
        }
        return false;
    };

    while (now != y)
        for (int to : grf[now])
            if (!vis[to] && reach(to, y)) {
                vis[to] = true, now = to, ans.push_back(now);
                break;
            }

    for (int x : ans) cout << x + 1 << " ";
    cout << endl;
}

int main() {
    int t;
    for (cin >> t; t; t--) solve();
}

Submission Info

Judge Result