fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. bool vis[105];
  4. int level[105];
  5. int parent[105];
  6.  
  7. vector<int> adj_list[105];
  8.  
  9. void bfs(int src) {
  10.     queue<int> q; 
  11.     q.push(src); //src ke queue te push kora
  12.     vis[src] = true; // src visited
  13.     level[src] = 0; // src er level 0 dhore nilam
  14.     parent[src] = -1; // src er parent -1 dhore nilam
  15.  
  16.     while(!q.empty()) {
  17.         int par = q.front();
  18.         q.pop();
  19.  
  20.         for(auto child: adj_list[par]) {
  21.             if(!vis[child]) {
  22.                 q.push(child);
  23.                 vis[child] = true;
  24.                 level[child] = level[par] + 1;
  25.                 parent[child] = par;
  26.             }
  27.         }
  28.     }
  29. }
  30.  
  31. int main() {
  32.     int n, e; cin >> n >> e;
  33.  
  34.     while(e--) {
  35.         int a, b; 
  36.         cin >> a >> b;
  37.         adj_list[a].push_back(b);
  38.         adj_list[b].push_back(a);
  39.     }
  40.  
  41.     bfs(0);
  42.  
  43.     int destination; cin >> destination;
  44.  
  45.     cout << "shortest distance from 0 to " << destination << " is = " << level[destination] << "\n";
  46.  
  47.     vector<int> path;
  48.  
  49.     int node = destination;
  50.  
  51.     while(node != -1) {
  52.         path.push_back(node);
  53.         node = parent[node];
  54.     }
  55.  
  56.     reverse(path.begin(), path.end());
  57.  
  58.     for(auto dir: path) {
  59.         cout << dir << " -> ";
  60.     }
  61.  
  62.     return 0;
  63. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
shortest distance from 0 to 2 is = 0
0 -> 2 ->
https://ideone.com/T7eP8n
language:
C++ (gcc 8.3)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!