nicuvlad76

Untitled

Nov 25th, 2020
504
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <fstream>
  2. #define N 105
  3. using namespace std;
  4. ifstream fin("BFS.in");
  5. ofstream fout("BFS.out");
  6. int n,m,nd;
  7. bool a[N][N], viz[N];
  8.  
  9. int prim, ultim, C[N];
  10. void Citire()
  11. {
  12.     int x,y;
  13.     fin>>n>>m>>nd;
  14.     while(fin>>x>>y)
  15.     {
  16.         a[x][y]=1;
  17.         a[y][x]=1;//neorientate
  18.     }
  19. }
  20. void Init(int nd)
  21. {
  22.    prim=ultim=1;
  23.    C[prim]=nd;
  24.    viz[nd]=1;
  25. }
  26. void BFS()///iterativ
  27. {
  28.    int varf;
  29.    while(prim<=ultim)
  30.    {
  31.       varf=C[prim++];
  32.       for(int k=1;k<=m;k++)
  33.         if(a[varf][k]==1 && viz[k]==0)
  34.       {
  35.           C[++ultim]=k;
  36.           viz[k]=1;
  37.       }
  38.    }
  39. }
  40. void BFS_r()///recursiv
  41. {
  42.    int varf;
  43.    if(prim<=ultim)
  44.    {
  45.       varf=C[prim++];
  46.       for(int k=1;k<=m;k++)
  47.         if(a[varf][k]==1 && viz[k]==0)
  48.       {
  49.           C[++ultim]=k;
  50.           viz[k]=1;
  51.       }
  52.       BFS_r();
  53.    }
  54. }
  55.  
  56. void Afisare()
  57. {
  58.   for(int i=1;i<=ultim;i++)
  59.         fout<<C[i]<<' ';
  60. }
  61. int main()
  62. {
  63.     Citire();
  64.     Init(nd);
  65.     BFS_r();
  66.     Afisare();
  67.     return 0;
  68. }
  69.  
RAW Paste Data