Advertisement
shawon_majid

messageRoute

Jun 5th, 2022
706
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.79 KB | None | 0 0
  1. //Bismillahir Rahman-ir Rahim
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define debug(x) cout << '>' << #x << " : " << x << endl;
  5. #define all(c) c.begin(), c.end()
  6. #define F first
  7. #define S second
  8. #define fastIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  9. typedef unsigned long long ull;
  10. typedef long long ll;
  11.  
  12. vector < int > adj[100006];
  13. int vis[100006]; // 0
  14. //
  15. // unordered_map < int, vector <int > > adj;
  16. int level[100006];
  17. int parent[100006];
  18.  
  19. void bfs(int source){
  20.  
  21.     queue < int > q;
  22.     q.push(source);
  23.     vis[source] = 1;
  24.     level[source] = 1;
  25.  
  26.     // cout << source << endl;
  27.  
  28.     while(!q.empty()){
  29.         int u = q.front();
  30.         q.pop();
  31.         for(int i = 0; i < adj[u].size(); i++){
  32.             int v = adj[u][i];
  33.             if(!vis[v]){
  34.                 vis[v] = 1;
  35.                 parent[v] = u;
  36.                 level[v] = level[u] + 1;
  37.                 // cout << v << endl;
  38.                 q.push(v);
  39.             }
  40.         }
  41.     }
  42.  
  43. }
  44.  
  45.  
  46. int main(){
  47.  
  48.     int n, e;
  49.     cin >> n >> e;
  50.  
  51.     // memset(vis, 0, sizeof vis);
  52.  
  53.     for(int i = 0; i < e; i++){
  54.         int a, b;
  55.         cin >> a >> b;
  56.         adj[a].push_back(b);
  57.         adj[b].push_back(a);
  58.     }
  59.  
  60.     bfs(1);
  61.  
  62.     if(vis[n]){
  63.         cout << level[n] << endl;
  64.         vector < int > ans;
  65.         int currentNode = n;
  66.         ans.push_back(n);
  67.         while(1){
  68.             currentNode = parent[currentNode];
  69.             ans.push_back(currentNode);
  70.             if(currentNode == 1){
  71.                 break;
  72.             }
  73.            
  74.         }
  75.         // ans.push_back(1);
  76.         reverse(all(ans));
  77.  
  78.         for(auto x: ans) cout << x << ' ';
  79.         cout << endl;
  80.  
  81.     }
  82.     else{
  83.         cout << "IMPOSSIBLE" << endl;
  84.     }
  85.  
  86.     return 0;
  87. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement