bfs.cpp

//#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <stack>

#define nln "\n"
#define long long long

const long N = 100010;

using namespace std;

fstream f1, f2;

inline void openf()
{
    f1.open("bfs.inp", ios:: in);
    f2.open("bfs.out", ios:: out);
}

static vector<vector<long>> a(N);
long n, m, s, f;

void data()
{
    f1.tie(0)->sync_with_stdio(0);
    f2.tie(0)->sync_with_stdio(0);

    f1 >> n >> m >> s >> f;
    for (size_t i = 0; i != m; ++i)
    {
        long x, y;
        f1 >> x >> y;
        a[x].push_back(y);
    }

    for (size_t i = 1; i-1 != n; ++i)
        sort(a[i].begin(), a[i].end());
}

static vector<bool> busy(N, 0);
static vector<long> road(N, 0);
static queue<long> que;


void process()
{
    // Breadth-First Searching
    que.push(s);
    busy[s] = 1;
    while (!que.empty())
    {
        long u = que.front();
        que.pop();
        for (const auto &i : a[u])
        {
            if (!busy[i])
            {
                road[i] = u;
                que.push(i);
                busy[i] = 1;
            }
        }
    }
}

void view()
{

    // Trace
    stack<long> rs;
    long co = 1;

    while (f != s && f != 0)
    {
        ++co;
        rs.push(f);
        f = road[f];
    }

    if (f != 0)
    {
        f2 << co << nln;
        rs.push(s);
        while (!rs.empty())
        {
            f2 << rs.top() << " ";
            rs.pop();
        }
    }
    else
        f2 << "0";
}

inline void closef()
{
    f1.close();
    f2.close();
}

int main()
{
    openf();
    data();
    process();
    view();
    closef();
    return 0;
}