sahadat49

BFS

Mar 25th, 2019
139
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.90 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #include<iostream>
  3. using namespace std;
  4. int bfs(int,int);
  5. int edge[100][100];
  6. int N,E;
  7. int main()
  8. {
  9. scanf("%d %d",&N,&E);
  10. int a,b;
  11. for(int i=0;i<100;i++)
  12. for(int j=0;j<100;j++)
  13. edge[i][j]=-1;
  14.  
  15. for(int i=0;i<E;i++){
  16. scanf("%d %d",&a,&b);
  17. edge[a][b]=1;
  18. edge[b][a]=1;
  19. }
  20. int start,end;
  21. scanf("%d %d",&start,&end);
  22. int x=bfs(start,end);
  23. if(x==1)
  24. printf("Possible to visit");
  25. else
  26. printf("Not Possible to visit");
  27. }
  28. int bfs(int start,int end){
  29. int visited[100];
  30. for(int i=0;i<100;i++)
  31. visited[i]=0;
  32. queue <int> q;
  33. q.push(start);
  34. while(q.empty()){
  35. int cur=q.front();
  36. q.pop();
  37. if(visited[cur]==-1)continue;
  38. visited[cur]=1;
  39. for(int i=0;i<N;i++)
  40. if(edge[cur][i]=1&& visited[i]==0)
  41. q.push(i);
  42. }
  43. return visited[end];
  44. }
Advertisement
Add Comment
Please, Sign In to add comment