fork download
copy 
  1. #include <bits/stdc++.h> 
  2. using namespace std;
  3. typedef long long int ll ; 
  4.  
  5.  
  6.  
  7. int main() {
  8.  
  9.     ll n ; 
  10.     cin>>n ; 
  11.     //taking input --> size of graph 
  12.  
  13.     ll m ; 
  14.     //taking input --> number of edges in the graph 
  15.     cin>>m ; 
  16.  
  17.     vector <ll> G[n+5]; //constructing a graph using adjacency list 
  18.  
  19.     ll i = 1 ; 
  20.     while(i<=m){
  21.  
  22.         ll u,v ; 
  23.         cin>>u>>v ; //reading the number of edges in the graph 
  24.         G[u].push_back(v);
  25.         G[v].push_back(u);
  26.         //making un directed graph jii 
  27.         i++;
  28.     }
  29.  
  30.  
  31.     queue <ll> q ; //declaring a queue  
  32.     ll source ;
  33. 	cin>>source;
  34.     q.push(source) ; //pushing the source node in the queue  
  35.  
  36.     ll used[n+5] = {0}; //declaring an empty used array where in used[i] = 0 means this node has not yet been visited in our algorithm
  37.     used[source] = 1 ; //source node has been visited hence setting it = 1 and it is inserted in the queue as well jiiiiii
  38.     ll lvl[n+5] = {0}; //declaring level array this basically lets us know level of each node jiiiii 
  39.     lvl[source] = 0 ; //lvl of source node which we mean the source node is 0 as we start from here jiiiiiiii
  40.  
  41.     while(!q.empty()){
  42.         //BFS Algo 
  43.  
  44.         ll v = q.front(); //top most element of queue jii
  45.  
  46.         q.pop(); //popping out the top most element of the queue jii........ 
  47.  
  48.         for(auto u : G[v]){
  49.             //this simply means you'r iterating through all nodes connected to node v 
  50.             if(used[u]==0){
  51.  
  52.                 //if the node u(node connected to v) has never been visited before then lets visit it jiii
  53.                 q.push(u);
  54.                 used[u] = 1 ; //it has now been visited hence setting its values as 1 
  55.                 lvl[u] = lvl[v] + 1 ; //lvl[u] will be 1 greater than lvl[1] as we move 1 step forward from u to v jiii 
  56.             } 
  57.  
  58.  
  59.         }
  60.  
  61.     }
  62.  
  63. 	i = 1 ; 
  64. 	while(i<=n){
  65. 		cout<<lvl[i]<<" ";//lvl[i] gives the shortest distance of each node from source.
  66. 		i++;
  67. 	}
  68.  
  69.     return 0 ; 
  70. }
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
5 4
1 2
2 3
2 4
3 5
2
stdout
copy 
1 0 1 1 2
https://ideone.com/ltvWtO
language:
C++ (gcc 8.3)
created:
3 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!