Advertisement
Guest User

Untitled

a guest
Jun 19th, 2019
66
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.13 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<int>node[10000];
  5. int parent[10000];
  6.  
  7. int bfc(int source,int destination)
  8. {
  9.     queue<int>q;
  10.     int arr[10000],dis;
  11.     q.push(source);
  12.     arr[source] = 1;
  13.     parent[source] = -1;
  14.     while(!q.empty()){
  15.         int n;
  16.         n = q.front();
  17.         q.pop();
  18.         for(int i = 0 ; i < node[n].size() ; i++ ){
  19.             if(node[n][i] == destination){dis = arr[n];parent[destination] = n;return dis;}
  20.             if(arr[node[n][i]] == NULL ){
  21.                 arr[node[n][i]] = arr[n] + 1;
  22.                 parent[node[n][i]] = n;
  23.                 q.push(node[n][i]);
  24.             }
  25.         }
  26.     }
  27. }
  28.  
  29. int main()
  30. {
  31.     int num_nodes,num_edges;
  32.  
  33.     cin >> num_nodes >> num_edges;
  34.  
  35.     for(int i = 0 ; i < num_edges ; i++){
  36.         int x , y;
  37.         cin >> x >> y;
  38.  
  39.         node[x].push_back(y);
  40.         node[y].push_back(x);
  41.     }
  42.     int beg,last;
  43.     cin >> beg >> last;
  44.     cout << bfc(beg,last)<<endl;
  45.     int n = last;
  46.     while(parent[n] != -1 ){
  47.         cout << n << " <- ";
  48.         n = parent[n];
  49.     }cout << beg << endl;
  50.  
  51.     return 0;
  52.  
  53. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement