CSES Problem Set Message Route Solution

 

Problem Link:  https://cses.fi/problemset/task/1667/

 Solution in C++:

///La ilaha illellahu muhammadur rasulullah

///******Bismillahir-Rahmanir-Rahim******///

///Abul Hasnat  Tonmoy

///Department of CSE,23rd batch

///Islamic University,Bangladesh

///**********ALLAH IS ALMIGHTY************///

#include <bits/stdc++.h>

using namespace std;

const int N = 100001;

bool vis[N];

vector<int> adj[N];

queue<int> q;

int dis[N], path[N];

void bfs(int n) {

  q.push(n);

  dis[1] = 1;

  while (!q.empty()) {

    int node = q.front();

    q.pop();

    for (int i = 0; i < adj[node].size(); i++) {

      int child = adj[node][i];

      if (!vis[child]) {

        vis[child] = true;

        dis[child] = dis[node] + 1;

        path[child] = node;

        q.push(child);

      }

    }

  }

}

int main() {

  int n, e;

  cin >> n >> e;

  while (e--) {

    int u, v;

    cin >> u >> v;

    adj[u].push_back(v);

    adj[v].push_back(u);

  }

  bfs(1);

  if (vis[n]) {

    cout << dis[n] << endl;

    vector<int> ans;

    int x = n;

    ans.push_back(n);

    while (x != 1) {

      x = path[x];

      ans.push_back(x);

    }

    reverse(ans.begin(), ans.end());

    for (int i = 0; i < ans.size(); i++) {

      cout << ans[i] << " ";

    }

    cout << endl;

  } else

    cout << "IMPOSSIBLE" << endl;

}