Advertisement
Guest User

Untitled

a guest
Sep 16th, 2019
133
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.34 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 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. //cout<<end<<endl;
  47. if(vis[end]==0){
  48. return 0;
  49. }
  50. else{
  51. printf("Possible\n");
  52. vector<int> path;
  53. path.push_back(end);
  54. int x=end;
  55. while(x!=start)
  56. {
  57. x=p[x];
  58. path.push_back(x);
  59. x--;
  60. }
  61. reverse(path.begin(),path.end());
  62. for(i=0;i<path.size();i++){
  63. cout<<path[i]<<" ";
  64. }
  65. }
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement