Advertisement
Guest User

Untitled

a guest
May 26th, 2019
88
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.87 KB | None | 0 0
  1. #include <fstream>
  2. #define N 105
  3.  
  4. using namespace std;
  5. ifstream fin("detdrum.in");
  6. ofstream fout("detdrum.out");
  7.  
  8. int a[N][N],n;
  9. int viz[N];
  10. int Q[N];
  11. int prim,ultim;
  12. int x;
  13. int rad;
  14. int V[N],m;
  15.  
  16. void Citire()
  17. { int i,y;
  18.   fin>>n>>x;
  19.   for(i=1;i<=n;i++)
  20.     { fin>>y;
  21.       if(y==0) rad=i;
  22.       a[y][0]++;
  23.       a[y][a[y][0]]=i;
  24.     }
  25. }
  26.  
  27. void BFS(int rad)
  28. { int v,i,y;
  29.   Q[1]=rad; prim=ultim=1;
  30.   viz[rad]=1;
  31.   m++;
  32.   V[m]=rad;
  33.   while(prim<=ultim && y!=x)
  34.      { v=Q[prim]; prim++;
  35.        for(i=1;i<=a[v][0];i++)
  36.          { y=a[v][i];
  37.            if(viz[y]==0)
  38.              { viz[y]=1;
  39.                ultim++; Q[ultim]=y;
  40.                m++;
  41.                V[m]=y;
  42.                if(y==x) return;
  43.              }
  44.          }
  45.      }
  46. }
  47.  
  48.  
  49. int main()
  50. { int i;
  51.   Citire();
  52.   BFS(rad);
  53.   for(i=m;i>=1;i--)
  54.     fout<<V[i]<<" ";
  55.     return 0;
  56. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement