CJPAYSBALLAS (lqdoj) - BFS

// https://lqdoj.edu.vn/problem/cjpaysballas
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;

int n, m, s, t;
vector<int> g[N];

bool visited[N];
int parent[N];
vector<int> path;

queue<int> q;

void BFS() {
    q.push(s);
    visited[s] = true;
    parent[s] = -1;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (u == t) break;

        for (int i = 0; i < (int) g[u].size(); i++) {
            int v = g[u][i];

            if (!visited[v]) {
                q.push(v);
                visited[v] = true;
                parent[v] = u;
            }
        }
    }
}

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#else
    freopen("CJPAYSBALLAS.inp", "r", stdin);
    freopen("CJPAYSBALLAS.out", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> s >> t;

    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
    }

    for (int i = 1; i <= n; i++)
        sort(g[i].begin(), g[i].end());

    BFS();

    int u = t;
    while (u != -1) {
        path.push_back(u);
        u = parent[u];
    }

    for (int i = (int) path.size() - 1; i >= 0; i--)
        cout << path[i] << ' ';

    return 0;
}