fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. vector <int>adj_list[100];
  4. int cost[100];
  5. int visited[100];
  6. int parent[100];
  7. vector <int> bfs;
  8. void BFS(int s){
  9.     cost[s]=0;
  10.     visited[s]=1;
  11.     parent[s]=s;
  12.  
  13.     queue<int>q;
  14.  
  15.     q.push(s);
  16.     while(!q.empty()){
  17.         int u=q.front();
  18.         q.pop();
  19.         bfs.push_back(u);
  20.  
  21.         for(int i=0;i<adj_list[u].size();i++){
  22.             int v = adj_list[u][i];
  23.  
  24.             if(visited[v]!=1){
  25.                 visited[v]=1;
  26.                 cost[v]=cost[u]+1;
  27.                 parent[v]=u;
  28.  
  29.                 q.push(v);
  30.             }
  31.         }
  32.     }
  33. }
  34. int main(){
  35.     int n,e;
  36.     cin>>n>>e;
  37.     for(int i=1;i<=e;i++){
  38.         int u,v;
  39.         cin>>u>>v;
  40.         adj_list[u].push_back(v);
  41.         adj_list[v].push_back(u); //unidrected hoile eta lage
  42.     }
  43.     int source,dest;
  44.     cin>>source>>dest;
  45.     BFS(source);
  46.     cout<<"Cost is: "<<cost[dest]<<"\n";
  47.  
  48.     vector<int>path;
  49.  
  50.     int now=dest;
  51.     path.push_back(now);
  52.  
  53.     while(parent[now]!=now){
  54.         now=parent[now];
  55.         path.push_back(now);
  56.     }
  57.     reverse(path.begin(),path.end());
  58.     cout<<"PATH IS: ";
  59.     for(int x:path){
  60.         cout<<x<<" ";
  61.     }
  62.     cout<<"\n";
  63.  
  64.     cout<<"BFS traversal IS: ";
  65.     for(int x:bfs){
  66.         cout<<x<<" ";
  67.     }
  68.     cout<<"\n";
  69.     return 0;
  70. }
  71. /*
  72. 7 8
  73.  
  74. 1 2
  75. 1 4
  76. 2 4
  77. 2 3
  78. 3 5
  79. 3 6
  80. 4 7
  81. 5 6
  82.  
  83. 1 5
  84. */
  85.  
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
7 8

1 2
1 4
2 4
2 3
3 5
3 6
4 7
5 6

1 5
stdout
copy 
Cost is: 3
PATH IS: 1 2 3 5 
BFS traversal IS: 1 2 4 3 7 5 6
https://ideone.com/MvGuYy
language:
C++ (gcc 8.3)
created:
11 hours 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!