Advertisement
Guest User

bfs

a guest
Apr 19th, 2019
111
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.82 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int bfs(vector<int>v[],int source,int n,int des)
  5. {
  6.     queue<int>q;
  7.     int level[n+1]={0};
  8.     q.push(source);
  9.     level[source]=1;
  10.     while(!q.empty())
  11.     {
  12.         int u=q.front();;
  13.         q.pop();
  14.         for(int i=0; i<v[u].size(); i++)
  15.         {
  16.             if(level[v[u][i]]==0)
  17.             {
  18.                 level[v[u][i]]=level[u]+1;
  19.                 q.push(i);
  20.                 if(v[u][i]==des)
  21.                 {
  22.                     return level[des];
  23.                 }
  24.             }
  25.         }
  26.     }
  27.  
  28. }
  29.  
  30. int main()
  31. {
  32.     int n,e,i,j,n1,n2;
  33.     cin>>n>>e;
  34.     vector<int>v[n+1];
  35.     for(i=0; i<e; i++)
  36.     {
  37.         cin>>n1>>n2;
  38.         v[n1].push_back(n2);
  39.     }
  40.     cout<<bfs(v,1,n,10)<<endl;
  41.     cout<<bfs(v,2,n,8)<<endl;
  42.     return 0;
  43. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement