Advertisement
askarulytarlan

обход в ширину

Jan 2nd, 2018
102
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.00 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int n, a, b, pr[5000], dist[5000], p[5000], ans;
  6. vector <int> x[5000];
  7. queue <int> q;
  8. int main(){
  9. cin >> n;
  10. for(int i = 1; i <= n; i++){
  11. for(int j = 1; j <= n; j++){
  12. cin >> a;
  13. if(a){
  14. x[i].push_back(j);
  15. x[j].push_back(i);
  16. }
  17. }
  18. }
  19. cin >> a >> b;
  20. q.push(a);
  21. pr[a] = 1;
  22. dist[a] = 0;
  23. p[a] = -1;
  24.  
  25. while(!q.empty()){
  26. int v = q.front();
  27. q.pop();
  28. for(int i = 0; i < x[v].size(); i++){
  29. int to = x[v][i];
  30. if(!pr[to]){
  31. pr[to] = 1;
  32. q.push(to);
  33. dist[to] = dist[v] + 1;
  34. p[to] = v;
  35. }
  36. }
  37. }
  38. if(!pr[b]){
  39. cout << -1;
  40. }
  41. else{
  42. vector <int> path;
  43. for(int i = b; i != -1; i = p[i]){
  44. path.push_back(i);
  45. ans++;
  46. }
  47. reverse(path.begin(), path.end());
  48. if(ans - 1){
  49. cout << ans - 1 << endl;
  50. for(int i = 0; i < path.size(); i++){
  51. cout << path[i] << " ";
  52. }
  53. }
  54. else{
  55. cout << ans - 1;
  56. }
  57. }
  58. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement