sahadat49

BFS everything

Apr 6th, 2019
117
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.42 KB | None | 0 0
  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 dist[100];
  8. int p[100];
  9.  
  10. int main()
  11. {
  12. scanf("%d %d",&node,&edge);
  13. int node1,node2;
  14. memset(adj,'-1',100);
  15. for(i=0;i<edge;i++){
  16. scanf("%d %d",&node1,&node2);
  17. adj[node1].push_back(node2);
  18. adj[node2].push_back(node1);
  19. }
  20. int start,end;
  21. scanf("%d %d",&start,&end);
  22. bfs(start,end);
  23. }
  24.  
  25. int bfs(int start,int end)
  26. {
  27. for(i=0;i<node;i++){
  28. vis[i]=0;
  29. }
  30. queue<int> q;
  31. q.push(start);
  32. vis[start]=1;
  33. while(!q.empty())
  34. {
  35. int u=q.front();
  36. q.pop();
  37. vis[u]=1;
  38. for(i=0;i<adj[u].size();i++){
  39. if(vis[adj[u][i]] == 0){
  40. int v=adj[u][i];
  41. vis[v]=1;
  42. dist[v]=dist[u]+1;
  43. p[v]=u;
  44. q.push(v);
  45. }
  46. }
  47. }
  48. //cout<<end<<endl;
  49. if(vis[end]==0){
  50. return 0;
  51. }
  52. else{
  53. printf("Possible\n");
  54. vector<int> path;
  55. path.push_back(end);
  56. int x=end;
  57. while(x!=start)
  58. {
  59. x=p[x];
  60. path.push_back(x);
  61. }
  62. reverse(path.begin(),path.end());
  63. for(i=0;i<path.size();i++){
  64. cout<<path[i]<<" ";
  65. }
  66. cout<<"distance "<<dist[end]<<endl;
  67. }
  68. }
Advertisement
Add Comment
Please, Sign In to add comment