fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long int ll ; 
  6.  
  7. int main() {
  8.  
  9.  
  10.     int n ;
  11.     cout<<"Number of nodes (vertices) in the graph: ";
  12.     cin>> n ; 
  13.     int m ;
  14.     cout<<"Number of edges in the graph: ";
  15.     cin>> m ;
  16.  
  17.  
  18.     //array of vectors to store adjacency list
  19.     vector <int> G[n+5] ; 
  20.  
  21.     int i = 1 ; 
  22.     while(i<=m){
  23.  
  24.         int x,y;
  25.         cout<<"Take the graph node and edges as input: "<<endl;
  26.         cin>>x>>y;
  27.  
  28.         //Graph is undirected
  29.         G[x].push_back(y);
  30.         G[y].push_back(x);
  31.  
  32.         i++;
  33.     }
  34.  
  35.  
  36.     //declaring a queue 
  37.     queue<int>q;
  38.     int source;//main node 
  39.     cout<<"Source: ";
  40.     cin>>source;
  41.  
  42.     q.push(source);//pushing the source node in the queue
  43.  
  44.     int visited[n+5]={0};//declaring an empty array 0 means its not visited
  45.  
  46.     visited[source]=1;//source node has been visited hence set it to = 1
  47.  
  48.     int level[n+5]={0};//declaring leveel array that tells us the level of each node
  49.  
  50.     level[source]=0;//lvl of source node which we mean the source node is 0 as we start from here
  51.  
  52.     while(!q.empty())
  53.     {
  54.         //BFS ALGO
  55.         int v=q.front();// Get the front element of the queue
  56.  
  57.         q.pop(); // Remove the front element
  58.  
  59.  
  60.        for(auto u: G[v])
  61.         {
  62.          //this simply means you'r iterating through all nodes connected to node y
  63.          if(visited[u]==0)// If node 'x' is not visited
  64.          {
  65.              q.push(u);// Push 'x' into queue
  66.              visited[u]=1;// Mark as visited
  67.              level[u]=level[v]+1;// Distance of 'x' = distance of 'y' + 1
  68.          }
  69.  
  70.         }
  71.     }
  72.  
  73.  
  74.     i = 1 ; 
  75. 	while(i<=n){
  76. 		cout<<level[i]<<" ";//lvl[i] gives the shortest distance of each node from source.
  77. 		i++;
  78. 	}
  79.  
  80.     return 0 ; 
  81. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
5
4
1 2
2 3
2 4
3 5
2
stdout
copy 
Number of nodes (vertices) in the graph: Number of edges in the graph: Take the graph node and edges as input: 
Take the graph node and edges as input: 
Take the graph node and edges as input: 
Take the graph node and edges as input: 
Source: 1 0 1 1 2
https://ideone.com/oukunl
language:
C++14 (gcc 8.3)
created:
10 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!