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.     //Start BFS from node 1
  36.     int source = 1 ; 
  37.     //Visited array (0 = not visited, 1 = visited)
  38.     int visited[n+5] = {0};
  39.     //Level array (stores shortest distance from source
  40.  
  41.     int level[n+5] = {0} ; 
  42.     //created a queue for bfs
  43.     queue <int> q ; 
  44.  
  45.     q.push(source);
  46.     visited[source] = 1 ; 
  47.     level[source] = 0 ; 
  48.     while(!q.empty()) {
  49.  
  50.         int removed = q.front();
  51.  
  52.         cout<<removed<<" ";
  53.         cout<<level[removed]<<"\n"; 
  54.         q.pop();
  55.  
  56.  
  57.  
  58.         for(auto u : G[removed]){
  59.             if(visited[u]==0) { 
  60.             q.push(u); 
  61.             visited[u] = 1;
  62.             level[u] = level[removed] + 1 ; 
  63.  
  64.  
  65.             }
  66.         }
  67.  
  68.  
  69.     }
  70.  
  71.     return 0 ; 
  72. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
10
8
1 2
1 3 
1 4
1 5
3 6
4 6
6 9
2 10
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: 
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: 
1 0
2 1
3 1
4 1
5 1
10 2
6 2
9 3
https://ideone.com/9wCMal
language:
C++14 (gcc 8.3)
created:
11 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!