মডিউল ১৪_৭ঃ Message Routes

Syrjälä নেটওয়ার্কে n কম্পিউটার এবং m সংযোগ রয়েছে। আপনার কাজ হল Uolevi কি Maija কে একটি বার্তা পাঠাতে পারে কিনা তা খুঁজে বের করা, এবং যদি এটি সম্ভব হয়, তাহলে এই জাতীয় route এ ন্যূনতম কম্পিউটারের সংখ্যা কত সেইটি বের করা।

প্রথম ইনপুট লাইনে দুটি পূর্ণসংখ্যা n এবং m রয়েছে: n হচ্ছে কম্পিউটার এবং m হচ্ছে সংযোগের সংখ্যা। কম্পিউটারের সংখ্যা 1,2,. . . .. , n। Uolevi এর কম্পিউটার 1 এবং Maija এর কম্পিউটার n ।

তারপর, m লাইন আছে। প্রতিটি লাইনে দুটি পূর্ণসংখ্যা a এবং b রয়েছে: সেই কম্পিউটারগুলির মধ্যে একটি সংযোগ রয়েছে। প্রতিটি সংযোগ দুটি ভিন্ন কম্পিউটারের মধ্যে, এবং যেকোনো দুটি কম্পিউটারের মধ্যে সর্বাধিক একটি সংযোগ থাকে।

সমাধানঃ

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
vector<int> v[N];
bool vis[N];
int parent[N];
void bfs(int s)
{
    queue<int> q;
    q.push(s);
    vis[s] = true;
    while (!q.empty())
    {
        int par = q.front();
        q.pop();
        for (int child : v[par])
        {
            if (!vis[child])
            {
                vis[child] = true;
                q.push(child);
                parent[child] = par;
            }
        }
    }
}
int main()
{
    int n, e;
    cin >> n >> e;
    while (e--)
    {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    memset(vis, false, sizeof(vis));
    memset(parent, -1, sizeof(parent));
    bfs(1);
    int x = n;
    vector<int> path;
    while (x != -1)
    {
        path.push_back(x);
        x = parent[x];
    }
    reverse(path.begin(), path.end());
    if (path.size() == 1)
        cout << "IMPOSSIBLE" << endl;
    else
    {
        cout << path.size() << endl;
        for (int val : path)
            cout << val << " ";
        cout << endl;
    }
    return 0;
}