SHARE
TWEET

BFS

sahadat49 Sep 16th, 2019 (edited) 89 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int bfs(int,int);
  4. vector<int>adj[100];
  5. int node,edge,i,j;
  6. int vis[100];
  7. int p[100];
  8.  
  9. int main()
  10. {
  11.     scanf("%d %d",&node,&edge);
  12.     int node1,node2;
  13.     memset(adj,'-1',100);
  14.     for(i=0;i<edge;i++){
  15.         scanf("%d %d",&node1,&node2);
  16.         adj[node1].push_back(node2);
  17.         adj[node2].push_back(node1);
  18.     }
  19.     int start,end;
  20.     scanf("%d %d",&start,&end);
  21.     bfs(start,end);
  22. }
  23.  
  24. int bfs(int start,int end)
  25. {
  26.     for(i=0;i<node;i++){
  27.         vis[i]=0;
  28.     }
  29.     queue<int> q;
  30.     q.push(start);
  31.     vis[start]=1;
  32.     while(!q.empty())
  33.     {
  34.         int u=q.front();
  35.         q.pop();
  36.         vis[u]=1;
  37.         for(i=0;i<adj[u].size();i++){
  38.             if(vis[adj[u][i]] == 0){
  39.                 int v=adj[u][i];
  40.                 vis[v]=1;
  41.                 p[v]=u;
  42.                 q.push(v);
  43.             }
  44.         }
  45.     }
  46.      if(vis[end]==0){
  47.         return 0;
  48.      }
  49.      else{
  50.         printf("Possible\n");
  51.         vector<int> path;
  52.         path.push_back(end);
  53.         int x=end;
  54.         while(x!=start)
  55.         {
  56.             x=p[x];
  57.             path.push_back(x);
  58.         }
  59.         reverse(path.begin(),path.end());
  60.         for(i=0;i<path.size();i++){
  61.                 cout<<path[i]<<" ";
  62.         }
  63.      }
  64. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top