fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int dist[20],par[20],vis[20];
  4. vector<int>adj_list[20];
  5. vector<int>BFS(int st,int dest)
  6. {
  7. vis[st]=1;
  8. par[st]=-1;
  9. dist[st]=0;
  10. queue<int>q;
  11. q.push(st);
  12. vector<int>path;
  13. while(!q.empty())
  14. {
  15. int fr=q.front();
  16. q.pop();
  17. for(int i=0;i<adj_list[fr].size();i++)
  18. {
  19. int adj=adj_list[fr][i];
  20. if(vis[adj]==0)
  21. {
  22. vis[adj]=1;
  23. par[adj]=fr;
  24. dist[adj]=dist[fr]+1;
  25. q.push(adj);
  26. if(adj==dest)
  27. {
  28. int curr=dest;
  29. while(curr!=-1)
  30. {
  31. path.push_back(curr);
  32. curr=par[curr];
  33. }
  34. return path;
  35. }
  36. }
  37. }
  38. }
  39. }
  40. int main()
  41. {
  42. int node,edge,id=0;
  43. cin>>node>>edge;
  44. map<char,int>mp;
  45. map<int,char>rev_mp;
  46. for(int i=1;i<=edge;i++)
  47. {
  48. string e;
  49. cin>>e;
  50. if(mp.find(e[0])==mp.end())
  51. {
  52. mp[e[0]]=id;
  53. rev_mp[id]=e[0];
  54. id++;
  55. }
  56. if(mp.find(e[1])==mp.end())
  57. {
  58. mp[e[1]]=id;
  59. rev_mp[id]=e[1];
  60. id++;
  61. }
  62. adj_list[mp[e[0]]].push_back(mp[e[1]]);
  63. }
  64. int st,dest;
  65. cin>>st>>dest;
  66. vector<int>result;
  67. result=BFS(mp[st],mp[dest]);
  68. cout<<dist[mp[dest]]<<endl;
  69. for(int i=result.size();i>=0;i--)
  70. {
  71. cout<<rev_mp[result[i]]<<" ";
  72. }
  73. }
  74.  
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
10
11
AB
BC
BD
AE
DE
DG
FE
HF
GH
GJ
HI
A
J
stdout
copy 
4
A A B D G J
https://ideone.com/ahS83w
language:
C++ (gcc 8.3)
created:
77 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!